22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

1
2
3
4
5
6
7
8
9
Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

1 <= n <= 8

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtracking("(", 1, 0, n, res);
        return res;
    }
    
    void backtracking(String s, int open, int closed, int n, List<String> res) {
        if (open + closed == 2 * n) {
            res.add(s);
            return;
        }
        if (open < n) 
            backtracking(s + "(", open + 1, closed, n, res);
        
        if (open > closed) 
            backtracking(s + ")", open, closed + 1, n, res);
    }
}

Solution#

Solution