代码随想录算法训练营第十八天｜LeetCode 77. 组合

今天是新篇章：回溯算法的第一天！

题目链接：77. 组合

状态：不了解回溯算法，所以前几题都是直接看解析做的，先体验一下。

回溯算法属于是暴力解法的一种，但是相比多层嵌套的for循环来讲，他能处理更多情况的问题。因为是暴力解法，所以可以形象的画成一个树形结构：第一次选1，第二次选2... 然后每次选择完之后下一层又可以接着选... （如下图）

回溯算法树形图

回溯的题目都会有一个模版代码，这一点在之后的回溯总结篇会讲到，所以在此我只去分享本题用回溯算法的思路。

void backtracking(参数) { // 模版代码
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

按照树形图的方式递归遍历，每次在遍历到叶子节点的时候就是收获果实的时候，然后在处理完果实的收获任务之后就退出当前层的选择，返回上一层去进行下一次选择，这样我们就可以实现先选[1,2]，然后把2退出去，再把3加进来，形成[1,3]...完整代码如下：

class Solution { //Java
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        combineHelper(n, k, 1);
        return result;
    }

    private void combineHelper(int n, int k, int startIndex){
        if(path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex; i <= n - (k - path.size()) + 1; i++){
            path.add(i);
            combineHelper(n, k, i + 1);
            path.removeLast();
        }
    }
}

复杂度分析：
时间复杂度：O(C(n,k) * k). 组合数C(n,k)表示在n个数中取k个数的所有可能组合，每次递归调用中都要遍历从startIndex到n的所有元素，总的调用次数和组合数C(n,k)成正比。每个组合都需要O(k)的时间来构建并添加到结果列表中，因为递归函数中每次递归调用都会向path中添加一个元素，直到path的长度为k。
空间复杂度：O(k).递归调用栈的最大深度为k，即每次递归调用最多使用O(k)的空间来存储路径path，额外的空间主要是存储结果列表result，但是这个是常数级别。

题目链接：216. 组合总和 III

状态：不了解回溯算法，所以前几题都是直接看解析做的，先体验一下。

本题就是在上一题的基础上增加了一个限制条件，即结果集的和为9. 那我们只需添加一个sum用来记录结果集的和就好了。

class Solution { // Java
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

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

    private void backTracking(int targetSum, int k, int startIndex, int sum) {
        // 减枝
        if (sum > targetSum) {
            return;
        }

        if (path.size() == k) {
            if (sum == targetSum) result.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, i + 1, sum);
            //回溯
            path.removeLast();
            //回溯
            sum -= i;
        }
    }
}

复杂度分析：
时间复杂度：O(C(9,k) * k). 分析同上题，只不过n确定为了9
空间复杂度：O(k). 分析同上题

题目链接：17. 电话号码的字母组合

状态：不了解回溯算法，所以前几题都是直接看解析做的，先体验一下。

本题就有两个地方不一样：1. 数字与字母之间如何做映射。2. 本题是从多个“池子”里挑选字母。所以树形结构也会有所变化，图示以及完整代码如下：

树形结构

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;

    }

    //每次迭代获取一个字符串，所以会涉及大量的字符串拼接，所以这里选择更为高效的 StringBuilder
    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);
        }
    }
}

复杂度分析略显复杂，稍后补充分享。

代码随想录算法训练营第十八天｜LeetCode 77. 组合