leetcode 22.括号生成

思路：dfs回溯

其实这道题看起来很像栈，但考虑到多种可能方案输出，我们需要用dfs来做。

乍一看好像没啥思路。我们可以从括号的特点入手，括号我们知道都是成对存在的，那么无论多少对括号，其实第一个符号肯定是'('，而最后一个符号肯定是')'。剩下的，我们就可以认为是在这个大括号里面进行排序了。

排序的时候我们需要注意三个点，其实就是dfs剪枝需要注意的三个点：

第一，当‘(’的个数比‘)’的个数少的时候，证明我们没有正确的括号来匹配了，也就是无效，这时不能匹配括号；

第二，当‘(’的个数要大于所给n的时候，说明我们的括号符号超过了，不能匹配；

第三，当')'的个数要大于所给n的时候，同理，不能匹配。

这样，我们再进行选择符号。

dfs中需要这么几个参数，string字符串:记录可能结果，用来存入集合当中；num1,num2分别表示'('和')'的个数；n是所给的括号对数。

针对于大括号中的每一个位置，我们都需要抉择是选择‘(’还是')'，不能不选。

这里首先就默认为字符串里面有第一个字符'('了。

最后在满足条件的情况下，再加入')'，之后存入集合才是正确的。因为这里dfs中我的'('个数是1，而')'个数是0，而不是1（有些人会想着把num2设置成1,其实也可以，改变一下满足条件即可）。

class Solution {List<String>list=new ArrayList<>();public List<String> generateParenthesis(int n) {StringBuilder buf=new StringBuilder();buf.append("(");dfs(buf,n,1,0);return list;}public void dfs(StringBuilder buf,int n,int num1,int num2){if(num1>n)return;if(num2>n)return ;if(num1<num2)return;if(num1+num2==n*2-1){buf.append(")");list.add(buf.toString());buf.deleteCharAt(buf.length()-1);return ;}buf.append(")");dfs(buf,n,num1,num2+1);buf.deleteCharAt(buf.length()-1);buf.append("(");dfs(buf,n,num1+1,num2);buf.deleteCharAt(buf.length()-1);}
}