回溯法(递归实现) Leetcode括号生成 + 电话号码_综合

1. 解题思路

1.1. 回溯问题

对串A逐个遍历, 且A中的每个元素都对应多个元素
- 此时使用回溯法
回溯法说到底就是两个方法,一个主一个辅
- 主的搞异常处理和初始化
- 辅的搞递归: 自己递归自己
辅助函数自己分类递归,有多少个可能就调用递归多少次
确定什么时候递归到头: 本题是rnum和lnum都到了n;电话号码是待转化的str遍历结束了

1.2. 代码

class Solution {
    // 结果private List<String> res=new ArrayList<String>();private void traceBack(int lnum,int rnum,String str,int n) {
    // 都是先左后右, 左括号数>=右括号数if(rnum==n) // 当右括号都结束时, 所有的都结束了res.add(str);else if(lnum==n) {
    // 左括号满了while(rnum++!=n) // 右括号加到满str+=")";res.add(str);//遍历结束}else if(rnum<lnum) {
    //有多少个可能就调用递归多少次traceBack(lnum+1, rnum, str+"(", n);traceBack(lnum, rnum+1, str+")", n);}else if(rnum==lnum)//特殊情况特殊分析(左右括号数相等,但还没遍历完)traceBack(lnum+1, rnum, str+"(", n);}public List<String> generateParenthesis(int n) {
    if(n<=0) return res;// 都是先左后右, 左括号数>=右括号数traceBack(1, 0, "(", n);return res;}
}

2. 电话号码(递归实现)

2.1. 思路

和本题"括号生成"一样,一个主函数一个辅函数
- 主函数搞异常,初始化
- 辅函数自己递归调用自己

2.2. 递归结束条件

if(leftChars.isEmpty()) {
    //为空是添加(遍历结束)res.add(comb);return;
}

2.3. 代码

	private List<String> res=new ArrayList<String>();private void backAdd(String comb,String leftChars) {
    if(leftChars==null) return;if(leftChars.isEmpty()) {
    //为空是添加(遍历结束)res.add(comb);return;}else {
    String letters=map.get(leftChars.charAt(0));for(int i=0;i!=letters.length();i++) {
    // 递归调用自己,有多少个可能就调用递归多少次backAdd(comb+letters.charAt(i),leftChars.substring(1));}}}public List<String> letterCombinations(String digits) {
    if(digits==null||digits.isEmpty()) return res;backAdd(new String(),digits);return res;}
``