今日题目
数字 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足：左括号必须以正确的顺序闭合。
示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1 输出：["()"]
提示：
1 <= n <= 8
思路
这道题其实还是挺有难度的，从头开始看下问题：数字 n 代表生成括号的对数，设计一个函数用于能够生成所有可能的并且有效的括号组合。
可以从另一个角度看成现有 2n 个空位，每个空位可以放置字符 '(' 或者 ')'，组成的所有括号组合中，有多少是合法的。
这个每个空位都判断一下也就是回溯法算在一个决策树的遍历过程，所以考虑用回溯算法
实现：
- 第一步确定路径：也就是已经做出的选择
- 第二步选择列表：也就是当前可以做的选择。
- 第三步确定结束条件：也就是到达决策树底层(选择列表为空的时候)，无法再做出选择的条件。
我们再看下一题目要求，对于符合条件的括号，必然包含的条件就是左括号和右括号数量是相等的，而且左括号必然在前面更早的位置出现，也就是说对于一个 "合法" 的括号字符串 s，必然对于任何 0 <= i < len(s) 都有：子串 s[0, i]中左括号的数量都大于或等于右括号的数量。
对于 2n个位置，必然有 n 个左括号和 n 个右括号，通过两个计数器来统计左右括号的个数，其中用 left 记录还可以使用多少个左括号，用right 记录还可以使用多少个右括号。
对于n个括号，left和right的初始值均为n，然后依次减少。
如果在该层添加了一个左括号，即 curStr + "("并且在下一层满足了结束条件，此时回溯到上一层时，当前的括号字符串仍为 curStr为没有添加 "(" 之前的括号字符串，判断其他的方式是否满足，回退重新选择，然后继续判断可使用的右括号的数量是否大于零，即 right > 0则 curStr + ")"，然后继续判断。
如果当前遍历的还可以使用的左括号数 > 还可以使用的右括号数，即 left > right 此时一定不可能生成一个 符合条件的括号字符串，直接回溯到上一层即可。
if (left < 0 || right < 0 || left > right){ return ; }
判断的过程中需要依次把left和right拿出来比较，看是否满足条件
如果left > 0，则尝试添加一个左括号；
如果right > 0，则尝试添加一个右括号。
// 添加一个左括号 if (left > 0) { trackback(left - 1, right, curStr + "("); } // 添加一个右括号 if (right > 0) { trackback(left, right - 1, curStr + ")"); }
定义什么时候结束，结束的时候必然是计数器都为0的时候，也就是可以使用的左括号数和右括号数同时为 0时，则表示当前的括号字符串 "合法"，将其添加到 结果 集合后，回溯到上一层即可。
代码实现
List<String> res = new ArrayList<>(); public List<String> generateParenthesis(int n) { String curStr = ""; trackback(n, n, curStr); return res; } public void trackback(int left, int right, String curStr) { if (left == 0 && right == 0) { res.add(curStr); return; } if (left < 0 || right < 0 || left > right) { return; } // 添加一个左括号 if (left > 0) { trackback(left - 1, right, curStr + "("); } // 添加一个右括号 if (right > 0) { trackback(left, right - 1, curStr + ")"); } }
执行用时：1 ms, 在所有 Java 提交中击败了74.05%的用户
内存消耗：38.2 MB, 在所有 Java 提交中击败了93.78%的用户
