The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Miscellaneous

Problem :-
Given the number of parenthesis pairs, print all possible combination of Balanced Parenthesis.
Suppose no. of parenthesis pairs = 3
Possible combination of Balanced Parenthesis are :-
{ } { } { }  |  { } { { } }  |  { { } } { }  |  { { } { } }  |  { { { } } }

Solution :-
The implementation shown below uses a recursive approach to print the combinations of balanced parenthesis keeping track of the number of open parenthesis and closed parenthesis at any point of recursion.
At any point, we have two possible options :
1 ) Print a open parenthesis ( if available ) and recursively check for a possible solution.
2 ) Print a closed parenthesis ( if a corresponding open parenthesis has been printed ) and recursively check for a possible solution.
We consider both the options at each point of recursion to print all possible combinations of balanced parenthesis. See the implementation below.

#include<iostream>
#define MAX_SIZE 100
using namespace std;

// print all possible combination of balanced parenthesis
// recursively
// open -> no. of open parenthesis considered so far
// close -> no. of closed parenthesis considered so far
void parenthesis(int pos, int n, int open, int close) {
   // character array to store a combination
   static char str[MAX_SIZE];

   if (close == n) {
      // print the combination
      cout<<str<<"\n";
   }
   else {
      if(open > close) {
         str[pos] = '}';
         parenthesis(pos+1, n, open, close+1);
      }
      if(open < n) {
         str[pos] = '{';
         parenthesis(pos+1, n, open+1, close);
      }
   }
}

// Wrapper function
void printParenthesis(int n) {
   if (n > 0) {
      parenthesis(0, n, 0, 0);
   }
}

// main
int main() {
   int n = 3;
   cout<<"\nPossible combinations are :-\n";
   printParenthesis(n);
   cout<<endl;
   return 0;
}

Back | Next

All Miscellaneous Problems
* Print all possible permutation of array elements
* Given the number of parenthesis pairs, print all possible combination of Balanced Parenthesis
* Given a set with 'n' elements, print subsets of all possible sizes
* Given a triangle in the form of a lower diagonal matrix, find the weight of maximum path in the triangle
* Given a matrix of 0s & 1s, find the maximum size square submatrix with all values as 1
* Given a set with 'n' elements. Find the sum of maximum elements in all subsets of size 'p' such that p <= n
* Given 2 strings, find all possible interleaved combination of the characters of the 2 strings