代码随想录算法训练营第二十五天 | ● 216.组合总和III ● 17.电话号码的字母组合

今日内容：

● 216.组合总和III

● 17.电话号码的字母组合

详细布置

216.组合总和III

如果把 组合问题理解了，本题就容易一些了。

题目链接/文章讲解：https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html

视频讲解：https://www.bilibili.com/video/BV1wg411873x

class Solution {
    List<List<Integer>> res = new ArrayList<>();//存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();//用来存放符合条件结果

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

    private void backTracking(int targetSum, int k,int sum, int startIndex){
        //剪枝
        if (sum > targetSum){
            return;
        }
        //终止条件
        if (path.size() == k){
            if (sum == targetSum){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        //剪枝9-(k - path.size())+1
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            path.add(i);//处理结点
            sum += i;
            backTracking(targetSum,k,sum,i + 1);//递归
            path.removeLast();//回溯，撤销处理的结点
            sum -= i;
        }
    }
}

17.电话号码的字母组合

本题大家刚开始做会有点难度，先自己思考20min，没思路就直接看题解。

题目链接/文章讲解：https://programmercarl.com/0017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E6%AF%8D%E7%BB%84%E5%90%88.html

视频讲解：https://www.bilibili.com/video/BV1yV4y1V7Ug遍历的深度，就是输入"23"的长度，而叶子节点就是我们要收集的结果，输出["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。

class Solution {
    //设置全局列表存储最后的结果
    List<String> list = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return list;
        }
        //初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
        String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        backTracking(digits, numString, 0);
        return list;
    }

    //每次迭代获取一个字符串，所以会设计大量的字符串拼接，所以这里选择更为高效的 StringBuild
    StringBuilder temp = new StringBuilder();

    //比如digits如果为"23",num 为0，则str表示2对应的 abc
    public void backTracking(String digits, String[] numString, int num) {
        //遍历全部一次记录一次得到的字符串
        if (num == digits.length()) {
            list.add(temp.toString());
            return;
        }
        //str 表示当前num对应的字符串
        String str = numString[digits.charAt(num) - '0'];
        for (int i = 0; i < str.length(); i++) {
            temp.append(str.charAt(i));
            backTracking(digits, numString, num + 1);
            //剔除末尾的继续尝试
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}