Problem description:

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:

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution:

The idea of this question is to use backtracking and dfs. Design a dfs helper function with left and right input. Everytime when we add a left parentheses (, we subtract left by 1, and increase right by 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        self.permutation(res, "", n, 0)
        return res
    def permutation(self, res, tmp, l, r):
        if l == r == 0:
            res.append(tmp)
            return
        if l > 0:
            self.permutation(res, tmp+ '(', l-1, r+1)
        if r > 0:
            self.permutation(res, tmp+ ')', l, r-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        string tmp= "";
        vector<string> res;
        helper(res, tmp, n, 0);
        return res;
    }
    
    void helper(vector<string>& res, string tmp, int left, int right){
        if(left==0 && right== 0){
            res.push_back(tmp);
            return;
        }
        
        if(right> 0)
            helper(res, tmp+")", left, right-1);
        if(left> 0)
            helper(res, tmp+"(", left-1, right+1);       
    }
};

time complexity: $O(2^n)$
space complexity: $O(n)$
reference: