Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

This is a classic problem involving Catalan numbers.
Catalan numbers is calculated using 

Catalann = (1/n+1)2nCn

There are many counting problems in combinatorics whose solution is given by the Catalan numbers.

• C_n is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's . For example, the following are the Dyck words of length 6:

        XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.

• Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, C_n counts the number of expressions containing n pairs of parentheses which are correctly matched:

         ((()))     ()(())     ()()()     (())()     (()())

 

In our case for n =3, we get 5 combinations as can be calculated.

 

We solve this problem using recursion. The basic idea is we keep 2 stocks of parentheses. Open and  Close. 

The combinations are made by picking parentheses from these stocks. When both these stocks are empty, we end up with one particular combination. We store it in our string vector and the recursion lets us find other combinations. Here's the code for it : 

  

class Solution {
public:
    vector generateParenthesis(int n) {

      vector ans;
      if (n>0) brackets(ans, "", n, 0);
      return ans;  

    }

    void brackets(vector & ans, string s, int openStock,  int closeStock) {
    if (openStock==0 && closeStock==0) ans.push_back(s);
 
   if(openStock>0) brackets(ans, s+"(", openStock-1, closeStock+1);
   if(closeStock>0) brackets(ans, s+")", openStock, closeStock-1);
}
};  

To understand, try dry run for n =2. It will help you understand better.