22. Generate Parentheses

,

Backtracking

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
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> resultList = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        backtrack(resultList, sb, 0, 0, n);
        return resultList;
    }

    private void backtrack(List<String> resultList, StringBuilder sb, int leftBracketCount, int rightBracketCount, int maxPairCount) {
        if (leftBracketCount + rightBracketCount == maxPairCount * 2) {
            resultList.add(sb.toString());
            return;
        }

        if (leftBracketCount < maxPairCount) {
            sb.append('(');
            backtrack(resultList, sb, leftBracketCount + 1, rightBracketCount, maxPairCount);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (rightBracketCount < leftBracketCount) {
            sb.append(')');
            backtrack(resultList, sb, leftBracketCount, rightBracketCount + 1, maxPairCount);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

Backtracking

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
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> resultList = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        dfs(resultList, sb, 0, 0, n);
        return resultList;
    }

    private void dfs(List<String> resultList, StringBuilder sb, int leftBrackets, int rightBrackets, int n) {
        if (rightBrackets > leftBrackets) {
            return;
        }
        if (leftBrackets > n) {
            return;
        }
        if (leftBrackets == n && rightBrackets == n) {
            resultList.add(sb.toString());
            return;
        }

        sb.append("(");
        dfs(resultList, sb, leftBrackets + 1, rightBrackets, n);
        sb.deleteCharAt(sb.length() - 1);

        sb.append(")");
        dfs(resultList, sb, leftBrackets, rightBrackets + 1, n);
        sb.deleteCharAt(sb.length() - 1);
    }
}

References

22. Generate Parentheses
剑指 Offer II 085. 生成匹配的括号