526互联

算法学习Day25回溯、组合总和

发布时间 2024-01-07 17:14:27作者: HQWQF

Day25回溯、组合总和

By HQWQF 2024/01/07

笔记

216.组合总和III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

回溯法

和上一道比较类似，到达目标长度就验证，使用startIndex来避免组合重复和重复数字。初步的剪枝也使用了相近的方法

class Solution {
private:
    vector<vector<int>> result; // 存放符合条件结果的集合
    vector<int> path; // 用来存放符合条件结果
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            int sum = 0;
            for(int i = 0;i < k;i++)
            {
                sum += path[i];
            }
            if(sum == n){result.push_back(path);}
            return;
        }
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            path.push_back(i); // 处理节点
            backtracking(n, k, i + 1); // 递归
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        result.clear(); // 可以不写
        path.clear();   // 可以不写
        backtracking(n, k, 1);
        return result;
    }
};

剪枝

但是，针对这一题我们可以进一步地剪枝，容易想到，如果在递归过程中累加sum变量而不是到目标长度再验证，我们就可以在sum变量超过目标值n时直接放弃该分支回溯。

class Solution {
private:
    vector<vector<int>> result; // 存放符合条件结果的集合
    vector<int> path; // 用来存放符合条件结果
    void backtracking(int n, int k,int sum, int startIndex) {
        if(sum > n){return;}
        if (path.size() == k) {
            if(sum == n){result.push_back(path);}
            return;
        }
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            path.push_back(i); // 处理节点
            backtracking(n, k,sum + i, i + 1); // 递归
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        result.clear(); // 可以不写
        path.clear();   // 可以不写
        backtracking(n, k,0, 1);
        return result;
    }
};

17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入： digits = "23"输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

回溯算法

使用回溯法解决组合问题的常规应用，没什么好说的，代码如下：

class Solution {
private:
    vector<string> result; // 存放符合条件结果的集合
    string path; // 用来存放符合条件结果
    const string letterMap[10] = {
    "", // 0
    "", // 1
    "abc", // 2
    "def", // 3
    "ghi", // 4
    "jkl", // 5
    "mno", // 6
    "pqrs", // 7
    "tuv", // 8
    "wxyz", // 9
};
    void backtracking(string digits,int stringIndex) {
        if (path.size() == digits.size()) {
            result.push_back(path);
            return;
        }
        string ABC =  letterMap[digits[stringIndex] - '0'];
        for (int i = 0; i < ABC.size(); i++) {
            path.push_back(ABC[i]); // 处理节点
            backtracking(digits,stringIndex + 1); // 递归
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }    
public:
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0)return result;
        backtracking(digits,0);
        return result;
    }
};