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
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

(n!) slow recursive solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
    public List<String> generateParenthesis(int n) {
        HashSet<String> result = generate(n);
        return new ArrayList<String>(result);
    }
    
    public HashSet<String> generate(int n) {
        if (n <= 0) {
            return null;
        } else if (n == 1) {
            HashSet<String> result = new HashSet<String>();
            result.add("()");
            return result;
        } else {
            HashSet<String> prev = generate(n - 1);
            HashSet<String> cur  = new HashSet<String>();
            for (String comb : prev) {
                insertPair(comb, cur);        
            }
            return cur;
        }
    }
  
    public void insertPair(String comb, HashSet<String> result) {
        result.add("()" + comb);
        for (int i = 0; i < comb.length(); i++) {
            result.add(comb.substring(0, i) + "()" + comb.substring(i, comb.length()));
        }
        result.add(comb + "()");
        result.add("(" + comb + ")");
    }
}

Backtracking solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<String> generateParenthesis(int n) {
     List<String> res = new ArrayList<>();
     helper(res, new StringBuilder(), 0, 0, n);
     return res;
}

private void helper(List<String> res, StringBuilder sb, int open, int close, int n) {
    if(open == n && close == n) {
        res.add(sb.toString());
        return;
    }
    
    if(open < n) {
        sb.append("(");
        helper(res, sb, open+1, close, n);
        sb.setLength(sb.length()-1);
    } 
    if(close < open) {
        sb.append(")");
        helper(res, sb, open, close+1, n);
        sb.setLength(sb.length()-1);
    }
}