22. Generate Parentheses

We need to count the left and right parentheses. We start from n left parentheses and 0 right parentheses. When we place 1 left parentheses, we need to decrease the left parentheses count by 1 but increase the right parentheses count by 1. When we place 1 right parentheses, we only need to decrease the right parenthese count by 1. Note the two cases above are not exclusive to each other. When there is no more left and right parentheses, we stop and push the solution to the result.

1:  class Solution {  
2:  public:  
3:    vector<string> generateParenthesis(int n) {  
4:      vector<string> res;  
5:      helper(n, 0, "", res);  
6:      return res;  
7:    }  
8:    void helper(int l, int r, string sol, vector<string> &res) {  
9:      if (l == 0 && r == 0) {  
10:        res.push_back(sol);  
11:        return;  
12:      }  
13:      if (l > 0) helper(l-1, r+1, sol+"(", res);  
14:      if (r > 0) helper(l, r-1, sol+")", res);  
15:    }  
16:  };