代码随想录算法训练营 DAY 25 | 216.组合总和III 17.电话号码的字母组合

216.组合总和III

直接在77的基础上修改，参数多了个sum，终止条件改成两个if嵌套，先判断大小=k，再判断sum=n，否则直接return！（不能合在一起判断，否则会栈溢出，无法return！）

• java代码

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    public void backtracking(int k, int target, int startIndex,int sum) {
        if (path.size() == k) {
            if (sum == target) {
                result.add(new ArrayList<>(path));
            }
            return; // 如果path.size() == k 但sum != n 直接返回
        }
        for(int i = startIndex; i <= 9 - (k-path.size()) + 1; i++) {
            sum+=i;
            path.add(i);
            
            backtracking(k,target,i+1,sum);
            sum-=i;
            path.removeLast();
            
        }
    } 

    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k,n,1,0);
        return result;
    }
}

17.电话号码的字母组合

• 关键：

1. 数字和字母如何映射 – 用一个String数组映射，作为回溯函数参数

//初始对应所有的数字，为了直接对应0-9，新增了两个无效的字符串""，对应0和1
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

2. for循环里的i的个数 = 这一位上所有可能的情况个数(numString[k].length())！
3. 每次递归用num表示当前位数。
4. 用一个List<String> result存储，用stringbuilder拼接，存进去之前先toString()转换一下。
5. 怎么用给的数字得到对应字符串？numString[digits.charAt(num) - '0']

回溯三部曲：

1. 确定回溯函数：传入映射数组，digits和num（表示当前要讨论的位数）

void backtracking(String digits, String[] numsString, int num)

2. 终止条件：num==digits长度了（num从0开始）

if(digits.length() == num) {  //收获结果
	result.add(sb.toString());
    return;
}

3. 单层逻辑

恢复现场用deleCharAt()方法，获得当前位数字对应的字符串用str = numsString[digits.charAt(num) - '0'];

 String str = numsString[digits.charAt(num) - '0'];
        for(int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            backtracking(digits,numsString,num+1);
            sb.deleteCharAt(sb.length()-1);  //恢复现场
        }

• java代码

class Solution {
    List<String> result = new ArrayList<>() ;
    StringBuilder sb = new StringBuilder(); 
    public void backtracking(String digits, String[] numsString, int num) {   
        if(digits.length() == num) {  //收获结果
            result.add(sb.toString());
            return;
        }
        String str = numsString[digits.charAt(num) - '0'];
        for(int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            backtracking(digits,numsString,num+1);
            sb.deleteCharAt(sb.length()-1);  //恢复现场
        }
    }   

    public List<String> letterCombinations(String digits) {
        String[] numsString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        if(digits.equals("")) return result;  //注意特殊情况 digits为空特殊判断
        backtracking(digits, numsString, 0);
        return result;
    }
}

Day25总结

1. 数字的list恢复现场用removeLast()，path数组是LinkedList

2. 字符串恢复现场用sb.deleteCharAt()

3. 电话号码题用String数组保存映射关系。

4. 取出String每一位上的可以直接str = numsString[digits.charAt(num) - '0']

5. 单层递归逻辑里for循环的次数就是 这一位上能填的值的情况总数！