想刷刷leetcode锻炼写自己写代码的能力，关于写代码，我觉得它不仅仅是写代码，而是写你的想法。为什么有的人会写成一坨，而有的人代码工整，美感，这个一方面是一个人写之前是否有思考清楚，另外一方面是写代码的习惯了。
代码只是表达思想的一种
题目
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
解题
首先想到的是，每一个位置都有两种可能性：2^6 = 64。
- 有一些很明显就错误的，比如："((( ((("
- 排除显而易见错误的，即左括号与右括号数量不等的
- 有错误不是那么明显看出来的，比如："))) (((" , "()) (()"
- 开头是右括号的，直接去掉，这个其实代表右括号已经出现的数量大于左括号出现的数量
正确的方案是，首先要放入左括号"("，后续要有一个与之对应的括号，同时在任何位置，有括号")"的数量不能大于"("的数量，否则,"())" 就是错误的。
代码
- 首先定义一个方法，要知道当前左括号与有括号的数量，并且知道当前的字符串
/**
*
* @param left 代表当前已经出现的左括号数量
* @param right 代表当前已经出现的右括号数量
* @param n 代表生成括号的对数
* @param s 代表当前的字符串，可能还未处理完
* @param res 保存所有括号字符串的列表
*/
private void generateParenthesis(int left, int right, int n, String s,List<String> res) {
}
- 目前比较喜欢的debug方式为通过打印，来看代码是否符合自己的预期，另外这次写一下终止条件
private void generateParenthesis(int left, int right, int n, String s,List<String> res) {
System.out.printf("当前的字符串为：%s ，左：%d，右%d \n",s,left,right);
// 终止条件
if (left == n && right == n){
res.add(s);
return;
}
...
}
- 中间的执行过程。首先要放入左括号，然后再放入有括号
private void generateParenthesis(int left, int right, int n, String s,List<String> res) {
System.out.printf("当前的字符串为：%s ，左：%d，右%d \n",s,left,right);
// 终止条件
if (left == n && right == n){
res.add(s);
return;
}
// 保证首先添加的是左括号
if (left < n){
generateParenthesis(left+1,right,n,s + "(",res);
}
// 注意，这里的right < left，代表的意思是
// 首先我们肯定要放入左括号才是合法的，这样的话，任何时刻，左括号的数量只能比右括号的数量多
if (right < n && right < left){
generateParenthesis(left,right+1,n,s + ")",res);
}
}
- 最终代码为
public class Solution_22 {
/**
* n = 3 生成
* [
* "((()))",
* "(()())",
* "(())()",
* "()(())",
* "()()()"
* ]
*
* 每一个位置都有两种可能性：2^6 = 64。
* 有一些很明显就错误的，比如："((( ((("
* - 排除显而易见错误的，即左括号与右括号数量不等的
* 有错误不是那么明显看出来的，比如："))) (((" , "()) (()"
* - 开头是右括号的，直接去掉，这个其实代表右括号已经出现的数量大于左括号出现的数量
*
* 正确的方案是首先放左括号，后面只需要有对应的右括号才行
*/
public static void main(String[] args) {
List<String> list = new Solution_22().generateParenthesis(3);
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
public List<String> generateParenthesis(int n) {
if(n == 0){
return Collections.emptyList();
}
List res = new LinkedList<String>();
generateParenthesis(0,0,n,"",res);
return res;
}
/**
*
* @param left 代表当前已经出现的左括号数量
* @param right 代表当前已经出现的右括号数量
* @param n 代表生成括号的对数
* @param s 代表当前的字符串，可能还未处理完
* @param res 保存所有括号字符串的列表
*/
private void generateParenthesis(int left, int right, int n, String s,List<String> res) {
System.out.printf("当前的字符串为：%s ，左：%d，右%d \n",s,left,right);
// 终止条件
if (left == n && right == n){
res.add(s);
return;
}
// 保证首先添加的是左括号
if (left < n){
generateParenthesis(left+1,right,n,s + "(",res);
}
// 注意，这里的right < left，代表的意思是
// 首先我们肯定要放入左括号才是合法的，这样的话，任何时刻，左括号的数量只能比右括号的数量多
if (right < n && right < left){
generateParenthesis(left,right+1,n,s + ")",res);
}
}
}
执行效果
image-20190421094040759
最后
递归的代码有一个问题，一般不能执行太多的层数，否则会堆栈错误。
