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

视频讲解：

还得用回溯算法！| LeetCode：17.电话号码的字母组合_哔哩哔哩_bilibili

和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III_哔哩哔哩_bilibili

216.组合总和III

思路：本题是?77.组合 的进阶，也是不重复地选择元素集合的K个元素形成结果，并且也需要主要的到的是元素选择所形成的集合是组合而非排列，因此当元素集合内元素有序时，选择的方向必须只有一个方向；其次本题额外多的条件是K个数和为n，添加至回溯模版内递归条件的终止条件部分。

// 时间复杂度上限会达到O(n^k)
// 空间复杂度上限O(n*(n-1)*(n-2)*……*(n-k+1))

class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        // 题目的本质就是K个数的组合，但是增加了K个数的和需要等于k，那么也就是进入结果集的组合少了
        // 不存在需要判断边缘条件的情况，因为给的参数里面不涉及会出现异常情况的数组或者字符串等引用类型的元素
        backtracking(0, n, k, 0, 0);
        return ans;
    }

    public void backtracking(int sum, int n, int k, int count, int index){
        if(count == k){
            if(sum == n)
                ans.add(new ArrayList<>(path));
            return;
        }

        // 剪枝条件
        int limit = 9-k+count+1;
        for(int i = index+1; i<=limit; i++){
            // 处理结果集
            sum += i;
            count++;
            path.add(i);
            backtracking(sum, n, k, count, i);
            path.remove(path.size()-1);
            // 回溯操作
            sum -= i;
            count--;
        }

        return;
    }
}

17.电话号码的字母组合

思路：首先明确题意是将字符串内的每个数字替换为3-4个字符中的一个；递归每一层遍历的是当前数字所对应的字符集内的所有字符，这与 组合问题以及组合问题||| 都是不同的，这两个问题的元素集合在每一次递归中都是共用的，每次都将从元素集合内选择部分元素，因此存在元素无法满足进行递归研究的可能，所以存在剪枝的可能。

而本题每一次递归都是访问的不同的元素集合，集合内每个元素都可以随机的选择，然后组合K个英文字母形成结果，不存在剪枝的可能。

采用回溯方法进行解题，就是首先明确访问的元素集合是什么，其次每一次访问元素集合元素集合有哪些要求（比如不可重复取、是组合而不是排列等等）；依据两个前提，将每次集合操作映射为递归步骤——访问元素可映射为元素处理、集合的要求可映射为各种判断条件；

在这样的思路确定下，沿用回溯模版解题。回溯问题，本质上就是将一个大问题划分为多个小问题，将可解的小问题完成后回溯拼接所有的小问题结果形成原问题的解答。所以一定要在读题时厘清题目中每个结果是如何形成的，每一步内容做的什么，从而形成小问题的认识，即可得到逐层递归所做的内容，例如每个数字对应的字符集遍历，选择一个数字之后下一次还可以选择的数字来加入当前的组合中。

// 时间复杂度O(3^m*4^n)，m,n分别为出现对应3个或4个字符集的数字的个数，也是每一次for循环遍历的范围
// 空间复杂度O(3^m*4^n)，一共有这么多种结果被产生

class Solution {
    
    List<String> ans = new ArrayList<>();
    StringBuilder builder = new StringBuilder();

    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.equals(""))
            return ans;

        List<char[]> list = new ArrayList<>();
        list.add(new char[]{'a','b','c'});          // 2
        list.add(new char[]{'d','e','f'});          // 3
        list.add(new char[]{'g','h','i'});          // 4
        list.add(new char[]{'j','k','l'});          // 5
        list.add(new char[]{'m','n','o'});          // 6
        list.add(new char[]{'p','q','r','s'});      // 7
        list.add(new char[]{'t','u','v'});          // 8
        list.add(new char[]{'w','x','y','z'});      // 9

        // 从第个数字开始
        backtracking(list, digits, 0);
        return ans;
    }

    public void backtracking(List<char[]> list, String digits, int index){
        // 终止条件
        if(index == digits.length()){
            ans.add(builder.toString());
            return;
        }
        // index代表当前访问到字符串内的第 index+1 个数字
        char ch = digits.charAt(index);
        // 获取当前数字对应的数组
        char[] arr = list.get(ch-'2');

        for(int i=0; i<arr.length; i++){
            // 处理结果集
            builder.append(arr[i]);
            backtracking(list, digits, index+1);
            builder.deleteCharAt(builder.length()-1);
        }

        return;
    }
}

?