LeetCode

1.题目2.思路3.代码实现（Java）

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

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

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

提示：
1 <= n <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses

（1）递归
主要思想如下（来自网络）：
① n=1时，显然结果为"()"；
② n=2时，我们可以在 n=1 的基础上进行括号组合，将n=1的结果进行拆解，得到"0 ( 1 ) 2"，即有0，1，2三个位置可以插入一个完整的"()"，那么可以直接得到"()()"，"(())"，"()()"，去重之后得到"()()"，"(())"；
③ n=3时，同理对n=2的所有结果进行拆解，在可以空缺的位置插入一个完整的"()"，去掉重复的便得到了最终的结果；
…
显然要想求出 n 对括号所有的有效组合，那必须先求出 n - 1 对括号的结果，如此类推，进而要求出 n = 1时的情况，而 n = 1时的结果我们很容易求出，就是"()"。所以我们可以使用递归的思想来进行求解。此外，需要注意的是，我们需要去掉重复结果，这一点可以使用Java中的 set 集合来解决。
（2）回溯算法
参考LeetCode官方题解。

//思路1————递归
public List generateParenthesis(int n) {
    if (n == 1) {
        return Arrays.asList("()");
    }
    HashSet hashSet = new HashSet<>();
    for (String str : generateParenthesis(n - 1)) {
        for (int i = 0; i <= str.length() / 2; i++) {
            hashSet.add(str.substring(0, i) + "()" + str.substring(i, str.length()));
        }
    }
    return new ArrayList<>(hashSet);
}

//思路2————回溯算法（来自LeetCode官方题解）
public List generateParenthesis(int n) {
   //res用于保存最终结果
    List res = new ArrayList();
    backtrack(res, new StringBuilder(), 0, 0, n);
    return res;
}


public void backtrack(List res, StringBuilder cur, int left, int right, int n) {
    //如果cur的长度 = 2 * n，说明已经找到了一种组合
    if (cur.length() == n * 2) {
        res.add(cur.toString());
        return;
    }
    //如果左括号数量小于 n，我们可以放一个左括号
    if (left < n) {
        cur.append('(');
        backtrack(res, cur, left + 1, right, n);
        cur.deleteCharAt(cur.length() - 1);
    }
    //如果右括号数量小于左括号的数量，可以放一个右括号。
    if (right < left) {
        cur.append(')');
        backtrack(res, cur, left, right + 1, n);
        cur.deleteCharAt(cur.length() - 1);
    }
}