[LeetCode] 22. Generate Parentheses

Posted on | In

Problem

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

Explanation

  1. Draw a tree and find out the trend. For example, when the input is 3:
1
2
3
4
5
6
7
8
9
                              (
                    /                   \
                   ((                    ()
                  /   \                  /
               (((      (()              ()(
               |       /   \            /     \
            ((()))  (()(     (())     ()((     ()()
                      |       |         |        |
                    (()())  (())()  ()(())     ()()()

  1. We notice that we can always add left paranthesis first until we have 3 left paranthesis.

  2. When we have 3 left paranthesis, we can only add right paranthesis. Or, when the number of right parantheis is less than the number of left paranthesis, we can add right paranthesis.

  3. The base case is when we have 3 right paranthesis, we need to return.

  4. We can debug the solution.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    void dfs(int n, int left, int right, StringBuilder sb, List<String> res) {
        if (right == n) {
            res.add(sb.toString());
            return;
        }
        if (left < n) {
            dfs(n, left+1, right, sb.append("("), res);
            sb.deleteCharAt(sb.length()-1);
        }
        if (right < left) {
            dfs(n, left, right+1, sb.append(")"), res);
            sb.deleteCharAt(sb.length()-1);
        }
    }
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        dfs(n, 0, 0, sb, res);
        return res;
    }
}