LeetCode：22. 括号生成

问题链接

22. 括号生成

问题描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

输入：n = 1
输出：["()"]

解题思路

这是一道标准的回溯题；
我们可以每一次添加一个括号：
如果(的数量小于n，我们可以添加一个(;
如果)的数量小于(的数量，我们可以选择添加一个)；
当(的数量达到n时，我们在后面只能添加)。

代码示例（JAVA）

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        backtrack(ans, n, 0, 0, new StringBuilder());
        return ans;
    }
    
    public void backtrack(List<String> ans, int n, int x, int y, StringBuilder str) {
        if (x == n) {
            for (; y < n; y++) {
                str.append(")");
            }
            ans.add(str.toString());
            return;
        }
        
        str.append("(");
        backtrack(ans, n, x + 1, y, new StringBuilder(str));
        
        if (y < x) {
            str.deleteCharAt(str.length() - 1);
            str.append(")");
            backtrack(ans, n, x, y + 1, new StringBuilder(str));
        }
    }
}