hot100 22.括号生成
思路：回溯。本质上来说，我们需要在0，1，2，...，2n - 1中选n个数（位置），填入左括号。其余n个位置填入右括号。所以本题是有额外约束的组合问题，对于括号字符串的任意前缀，右括号的个数不能超过左括号的个数，比如（））（就是不合法的。
一、方法一：枚举当前位置填左括号还是右括号。
1.本质：是“选或不选”的思想，可以把填左括号视作“选”，填右括号视作“不选”。
2.递归的过程中，要保证右括号的个数不能超过左括号的个数。
（1）如果现在右括号的个数等于左括号的个数，那么不能填右括号。
（2）如果现在右括号的个数小于左括号的个数，那么可以填右括号。
（3）如果左括号的个数始终大于等于右括号的个数，且至多填n个左括号，所以当我们填了n个右括号时，也一定填了n个左括号，此时填完了所有2n个括号。
3.疑问：什么时候需要写恢复现场，什么时候不需要写恢复现场？
答：
在下面的代码中，如果初始化path为空列表，那么就需要写恢复现场。本题由于所有的括号长度都是固定的2n，我们可以创建一个长为2n的path列表，在递归时直接写入字符（而不是插入字符），这样做无需写恢复现场。
4.复杂度分析：
（1）时间复杂度：分析回溯问题的时间复杂度，有一个通用公式：路径长度×搜索树的叶子数。对于本题，它等于O(n⋅C(2n,n))。但由于左右括号的约束，实际上没有那么多叶子，根据Catalan数，只有C(2n,n)/(n+1)个叶子节点，所以实际的时间复杂度为O(C(2n,n))。此外，根据阶乘的 Stirling公式，时间复杂度也可以表示为O(4^n/根号n)。
（2）空间复杂度：O(n)。返回值的空间不计入。
附代码：
class Solution { public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); char[] path = new char[n*2]; // 所有括号组合长度都是2n dfs(0,0,n,path,res); // 一开始没有填括号 return res; } // 目前填了left个左括号，right个右括号 private void dfs(int left,int right,int n,char[] path,List<String> res){ if(right == n){ // 填完了2n个括号 res.add(new String(path)); return; } if(left < n){ // 可以填左括号 path[left + right] = '('; // 直接覆盖，避免了显式恢复现场 dfs(left + 1,right,n,path,res); } if(right < left){ // 可以填右括号 path[left + right] = ')'; // 直接覆盖，避免了显式恢复现场 dfs(left,right + 1,n,path,res); } } }二、方法二：枚举下一个左括号的位置。
1.思路：用“枚举选哪个”的思路，也就是说在从左往右填的过程中，要时刻保证右括号的个数不能超过左括号的个数。
2.举例：如果前面填了5个左括号，2个右括号，那么至多还能填3个右括号。
所以，在填下一个左括号之前，枚举填入了0，1，2，3个右括号，这样就能得到下一个左括号的位置。
3.为了方便，代码直接使用balance表示左右括号之差，这样枚举的范围就是[0,balance]。
4.注意：最后一个左括号的右边还可以填右括号，但无需考虑。填入所有左括号后，剩余的位置我们会自动填入右括号。
5.复杂度分析：
（1）时间复杂度：分析回溯问题的时间复杂度，有一个通用公式：路径长度×搜索树的叶子数。对于本题，它等于O(n⋅C(2n,n))。但由于左右括号的约束，实际上没有那么多叶子，根据Catalan数，只有C(2n,n)/(n+1)个叶子节点，所以实际的时间复杂度为O(C(2n,n))。此外，根据阶乘的 Stirling公式，时间复杂度也可以表示为O(4^n/根号n)。
（2）空间复杂度：O(n)。返回值的空间不计入。
附代码：
class Solution { public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); List<Integer> path = new ArrayList<>(); dfs(0,0,n,path,res); return res; } // 目前填了i个括号 // 这i个括号中的左括号个数 - 右括号个数 = balance private void dfs(int i,int balance,int n,List<Integer> path,List<String> res){ if(path.size() == n){ char[] s = new char[n*2]; Arrays.fill(s,')'); for(int j : path){ s[j] = '('; } res.add(new String(s)); return; } // 枚举填right = 0,1,2,......,balance个右括号 for(int right = 0;right <= balance;right++){ // 先填right个右括号，然后填1个左括号，记录左括号的下标 i + right path.add(i + right); dfs(i + right + 1,balance - right + 1,n,path,res); path.removeLast(); // path.remove(path.size() - 1); } } }