代码随想录算法训练营打卡Day25 | LeetCode216 组合总和III、LeetCode17 电话号码的字母组合

摘要

剪枝操作并不会改变回溯算法的暴力搜索的本质，但确实可以减少一些不必要的搜索。
在单层递归中，要注意区分组合问题和排列问题，仔细分析结果的构造过程。

LeetCode77 组合

77. 组合 - 力扣（Leetcode）

先回顾一下没有剪枝的回溯

class Solution {
public:
    void backtracking(vector<vector<int>>& res, int& n, int& k, vector<int>& cur, int j) {
        if (cur.size() == k) {
            res.push_back(cur);
            return;
        }
        for (int i = j; i <= n; i++) {
            cur.push_back(i);
            backtracking(res, n, k, cur, i + 1);
            cur.pop_back();
        }
        return;
    } 
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> cur;
        backtracking(res, n, k, cur, 1);
        return res;
    }
};

剪枝前

剪枝前是28ms。
从答案的构造过程来看，不是所有的cur的size都能到达k，而且这是可以提前判断的。当剩余能加入组合的元素不足以让cur.size()达到k时，就不需要再搜索这个节点之后的子树。
例如n = 4, k = 4，其答案构造过程的树形如下

答案构造过程的树

可见，当剩余能加入组合元素的个数已经不足以让cur.size()达到k时，就不需要再向下搜索。体现在上述例子中，比如第二层的{2}、{3}、{4}，向下构造答案，都不能再加入3个数使得cur.size()达到k，所以是不需要再搜索的，可以直接剪枝。
本题的剪枝条件为剩余可选元素个数不足以让组合中的元素个数达到k。体现在代码中就是for语句的循环条件。即集合中剩余可选元素个数n-i >= 所需需要的元素个数k - path.size()。

class Solution {
public:
    void backtracking(vector<vector<int>>& res, int& n, int& k, vector<int>& cur, int j) {
        if (cur.size() == k) {
            res.push_back(cur);
            return;
        }
        for (int i = j; i <= n - (k - cur.size()) + 1; i++) {
            cur.push_back(i);
            backtracking(res, n, k, cur, i + 1);
            cur.pop_back();
        }
        return;
    } 
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> cur;
        backtracking(res, n, k, cur, 1);
        return res;
    }
};

剪枝后

可见剪枝能在一定程度上提升回溯法的性能。

LeetCode216 组合总和III

216. 组合总和 III - 力扣（Leetcode）

初见题目的想法：和组合问题类似。复习回溯法的思考步骤：
- 确定递归函数的终止条件：当前组合的元素个数等于k；需要注意的是递归的终止条件不一定是收集答案的条件，在这道题中还要加额外的判断，即当前组合内元素的和为n时才收集答案。
- 在分析问题的过程中确定递归函数需要的参数：
- 确定单层递归的处理逻辑
- 思考可能的剪枝条件

初见的题解代码如下，只考虑了使用最大和和最小和来进行剪枝

class Solution {
public:
    void backtracking(int& k, int& n, vector<vector<int>>& res, 
                    vector<int>& cur, int& sum, int start) 
    {
        if (cur.size() == k) {
            if (sum == n) res.push_back(cur);
            return;
        }
        for (int i = start; i <= 9; i++) {
            cur.push_back(i);
            sum += i;
            backtracking(k, n, res, cur, sum, i + 1);
            sum -= i;
            cur.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        
        int minSum = 0;
        for (int i = 1; i <= k; i++) minSum += i;
        if (n < minSum) return res;

        int maxSum = 0;
        for (int i = 9; i > 9 - k; i--) maxSum += i;
        if (n > maxSum) return res;

        vector<int> cur;
        int sum = 0;
        int start = 1;
        backtracking(k, n, res, cur, sum, start);
        return res;
    }
};

剪枝：由于sum是递增的，如果当前的sum已经大于n，则不需要再向下搜索。

添加剪枝条件的题解代码，有两种实现方式，一是在递归终止条件里添加，二是在for循环中添加

通过递归终止条件进行剪枝

void backtracking(int& k, int& n, vector<vector<int>>& res, 
                vector<int>& cur, int& sum, int start) 
{
    if (sum > n) return;
    if (cur.size() == k) {
        if (sum == n) res.push_back(cur);
        return;
    }
    for (int i = start; i <= 9; i++) {
        cur.push_back(i);
        sum += i;
        backtracking(k, n, res, cur, sum, i + 1);
        sum -= i;
        cur.pop_back();
    }
}

在for循环中进行剪枝

void backtracking(int& k, int& n, vector<vector<int>>& res, 
                    vector<int>& cur, int& sum, int start) 
{   
    if (cur.size() == k) {
        if (sum == n) res.push_back(cur);
        return;
    }
    for (int i = start; i <= 9; i++) {
        cur.push_back(i);
        sum += i;
        if (sum <= n) backtracking(k, n, res, cur, sum, i + 1);
        sum -= i;
        cur.pop_back();
    }
}

LeetCode17 电话号码的字母组合

17. 电话号码的字母组合 - 力扣（Leetcode）

初见题目时的想法：按回溯法的三部曲进行思考
- 递归的终止条件：当前字母组合的长度与输入数字的长度相等，收集结果。
- 递归函数需要的参数：保存输入数字的字符串，收集结果的结果集，当前字母组合，当前处理到第几位输入数字。
- 单层递归的逻辑：遍历当前输入的数字对应的字母，向下搜索答案。

初见题目的题解代码如下

class Solution {
public:
    vector<char> button(char d) {
        switch (d) {
            case '2': return {'a', 'b', 'c'};
            case '3': return {'d', 'e', 'f'};
            case '4': return {'g', 'h', 'i'};
            case '5': return {'j', 'k', 'l'};
            case '6': return {'m', 'n', 'o'};
            case '7': return {'p', 'q', 'r', 's'};
            case '8': return {'t', 'u', 'v'};
            case '9': return {'w', 'x', 'y', 'z'};
            default: return {};
        }
    }
    void backtracking(const string& digits, vector<string>& res,
                    int start, string& cur)
    {
        if (cur.size() == digits.size()) {
            res.push_back(cur);
            return;
        }
        for (int i = start; i < digits.size(); i++) {
            for (auto& iter : button(digits[i])) {
                cur.push_back(iter);
                backtracking(digits, res, i + 1, cur);
                cur.pop_back();
            }
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if (digits.size() == 0) return res;
        string cur;
        backtracking(digits, res, 0, cur);
        return res;
    }
};

外面这一层for循环是没有必要的。
什么时候需要这外面一层的for循环呢？如果是组合问题，则需要外面这层for。如果是排列问题，则不需要这层for。因为输入数字是有序的，其对应的字母组合也是有序的，所以不存在跳过一个输入数字，去处理再下一位输入数字的情况，
- 其实有外面这层for循环也不影响结果，因为跳过一位输入数字会使得最终构造出的字母串不够长，不会被收入结果集。但是，这样会做很多不必要的搜索。

// for (int i = start; i < digits.size(); i++) {
    for (auto& iter : button(digits[i])) {
        cur.push_back(iter);
        backtracking(digits, res, i + 1, cur);
        cur.pop_back();
    }
// }

要对组合问题和排列问题做好区分。

修改后的题解代码如下

class Solution {
public:
    vector<char> button(char d) {
        switch (d) {
            case '2': return {'a', 'b', 'c'};
            case '3': return {'d', 'e', 'f'};
            case '4': return {'g', 'h', 'i'};
            case '5': return {'j', 'k', 'l'};
            case '6': return {'m', 'n', 'o'};
            case '7': return {'p', 'q', 'r', 's'};
            case '8': return {'t', 'u', 'v'};
            case '9': return {'w', 'x', 'y', 'z'};
            default: return {};
        }
    }
    void backtracking(const string& digits, vector<string>& res,
                    int start, string& cur)
    {
        if (cur.size() == digits.size()) {
            res.push_back(cur);
            return;
        }
        for (auto& iter : button(digits[start])) {
            cur.push_back(iter);
            backtracking(digits, res, start + 1, cur);
            cur.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if (digits.size() == 0) return res;
        string cur;
        backtracking(digits, res, 0, cur);
        return res;
    }
};