LeetCode 22. Generate Parentheses（括号生成）

题目

解析

思路：一开始我的思路是如何去对所有可能的情况进行遍历，最后再根据合理性排除掉不可能的解。输入的n为如何值都有可能，我没有办法通过循环去尝试组合。这里用到的是“（”和“）”两种符号，就像是0和1一样，这让我联想到了二叉树的遍历，二叉树的遍历是以递归的形式实现的，最终它可以遍历到每一个节点并且可以得到每个节点的唯一的01码（假设向左遍历字符串累加0，向右遍历字符串累加1）。这道题不也是对一个字符串进行生成吗？可以通过递归来实现求解。通过递归，我们可以得到所有的可能性，在递归的过程中可以通过条件判断结束不合理的情况，即“剪枝”，这又体现了回溯算法的思想。最初的条件，就是有多少个“（” 和 “）”以及初始空字符串“”。刚开始可以先用一个左括号，也可以使用一个右括号，针对这两种情况继续进行讨论不就是递归的思想吗？
为什么可以用递归？
因为初始条件是左括号数目，右括号数目，当前字符串。之后每一步的求解思路都是一样的，可以使用同一个方法去代。
剪枝：
当剩下的左括号数量大于右括号数量时，需要结束这个递归，因为剩下的符号都加在右边，右括号不够，不能形成闭合。

 if(left>right)
     return;

获取最终字符串：
左右括号都用完之后就可以获取最终字符串了。

if(left==0&&right==0){
    arrayList.add(s);
}

完整代码（Java实现）：

class Solution {
	ArrayList<String> arrayList=new ArrayList<>();
    public List<String> generateParenthesis(int n) {
          get(n, n, "");
          return arrayList;         
    }    
    public void get(int left,int right,String s){
    	   if(left>right)
    		   return;
    	   if(left>0){
    		   get(left-1,right,s+'(');
    	   }
    	   if(right>0){
    		   get(left, right-1, s+')');
    	   }
    	   if(left==0&&right==0){
    		   arrayList.add(s);
    	   }
    }        
}

另外一个递归的例子（17. Letter Combinations of a Phone Number）

题目：

分析：这里每一步的可以套用相同的模板。判断下一个字符是什么，然后根据数字对应的几个字母索引，更新结果字符串并开始新的递归。
代码：

class Solution {
	ArrayList<String> strings=new ArrayList<>();
	int len;
	String string;
    public List<String> letterCombinations(String digits) {
    	if(digits.length()==0){
    		return strings;
    	}
    	len=digits.length();
    	string=digits;
        get(0, "");
        return strings;
    }    
    public void get(int count,String result){
    	if(count<len){
    		char x=string.charAt(count);    		
	    	if(x=='2'){	    		
	    		get(count+1,result+"a");
	    		get(count+1,result+"b");
	    		get(count+1,result+"c");
	    	}
	    	else if(x=='3'){
	    		get(count+1, result+"d");
	    		get(count+1, result+"e");
	    		get(count+1, result+"f");
	    	}
	    	else if(x=='4'){
	    		get(count+1, result+"g");
	    		get(count+1, result+"h");
	    		get(count+1, result+"i");
	    	}
	    	else if(x=='5'){
	    		get(count+1, result+"j");
	    		get(count+1, result+"k");
	    		get(count+1, result+"l");
	    	}
	    	else if(x=='6'){
	    		get(count+1, result+"m");
	    		get(count+1, result+"n");
	    		get(count+1, result+"o");
	    	}
	    	else if(x=='7'){
	    		get(count+1, result+"p");
	    		get(count+1, result+"q");
	    		get(count+1, result+"r");
	    		get(count+1, result+"s");
	    	}
	    	else if(x=='8'){
	    		get(count+1, result+"t");
	    		get(count+1, result+"u");
	    		get(count+1, result+"v");
	    	}
	    	else if(x=='9'){
	    		get(count+1, result+"w");
	    		get(count+1, result+"x");
	    		get(count+1, result+"y");
	    		get(count+1, result+"z");
	    	}
    	}else{    	
    		strings.add(result);
    	}    	
    }    
}