LeetCode-22. 括号生成

题目来源
22. 括号生成

题目思路

回溯法，一般可以解决如下几种问题：

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

这道题的思路:就是不停选括号，要么选左括号，要么选右括号。
并有这些约束的：
只要(有剩，就可以选(。 (((((这么选，都还不能判定为非法。
当剩下的)比(多时，才可以选)，否则，)不能选，选了就非法。 因为：剩下的)比(少，即，使用的)比(多，不能成双成对。
举个简单的例子吧

n=2
如果()，接下来你选)就变成()),就不能成对了，那么只能选(

总结一句话:剩下的)比(多时，才可以选)，相等的话也只能选(

回溯法

• 1.确定回溯函数参数

首先需要一个字符串builder来收集叶子节点的结果，然后用一个字符串数组result保存起来，这两个变量我依然定义为全局。
我们要定义两个参数letf和right，分别表示左右括号

    List<String> result = new ArrayList<>();StringBuilder builder = new StringBuilder();void backtracking(int n ,int left,int right)

• 2.确定终止条件

如果builder字符长度等于n*2，得到最终结果，把它放进result里面
我来解释一下什么意思

当n=2时，那么其中一个结果就是(()),那么答案就是4个，满足就放进result里面

        if(builder.length() == n*2){result.add(String.valueOf(builder));return;}// 剪枝if (left < right) {return;}

• 3.确定单层遍历逻辑

if(left < n)表示最多能加多少个(

        if(left < n){builder.append("(");  //处理backtracking(n,left+1,right);builder.deleteCharAt(builder.length() - 1);  //回溯}if(right < n){builder.append(")"); //处理backtracking(n,left,right+1);builder.deleteCharAt(builder.length() - 1); //回溯}

代码实现

class Solution {List<String> result = new ArrayList<>();StringBuilder builder = new StringBuilder();public List<String> generateParenthesis(int n) {if(n == 0){return result;}backtracking(n,0,0);return result;}public void backtracking(int n ,int left,int right){if(builder.length() == n*2){result.add(String.valueOf(builder));return;}// 剪枝if (left < right) {return;}if(left < n){builder.append("(");backtracking(n,left+1,right);builder.deleteCharAt(builder.length() - 1);}if(right < n){builder.append(")");backtracking(n,left,right+1);builder.deleteCharAt(builder.length() - 1);}}
}

遇到的困难

对StringBuilder的api不熟悉

builder.append("(");   //添加
builder.deleteCharAt(builder.length() - 1);  //删除