回溯算法 四题

77.组合（回溯算法）--求组合数--只能使用一次

77.组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

class Solution {
    vector<vector<int>> result;//存储最终结果
    vector<int>path;//存储叶子节点
    void Back(int n,int k,int starIndex){
        if(path.size()==k){
            result.push_back(path);
            return;
        }
        //找叶子节点的值--优化--如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了--剪枝

        for(int i=starIndex;i<=n-(k-path.size())+1;i++){
            path.push_back(i);
            Back(n,k,i+1);
            //将找到的第二个值pop掉，方便下一个值进来
            path.pop_back();// 回溯，撤销处理的节点
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        Back(n,k,1);
        return result;
    }
};

1.明确result,和path的含义

result:存储最终的返回值。

path:存储每个叶子节点的值（每个组合的值）

2.确定递归终止条件（递归，纵向遍历，深入叶子节点，得到组合最终结果）

当叶子节点所得到的值的长度==k的长度时，说明递归终止，终止后将所得到的path的值存入result二维数组中

3.for循环的意义 （横向遍历—遍历数组长度）

将每次递归起始位置的值压入path数组，递归的查找下一个值，每次递归结束都将最后的值pop出，方便后续值的地回归

4.剪枝优化（去掉无意义的循环，留下需要的循环）

216.组合数3（回溯算法）--求组合数--只能使用一次

216.组合数3

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

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

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

class Solution {
    vector<vector<int>>result;
    vector<int>path;
    void Back(int k,int n,int starIndex){
        //如果当前的和已经大于目标和了，没必要进行下去了
        if(accumulate(path.begin(),path.end(),0)>n){
            return;
        }
        if(path.size()==k&&accumulate(path.begin(),path.end(),0)==n){
            result.push_back(path);
            return;
        }
               //必须要剪枝操作--要不会超时
        for(int i=starIndex;i <= 9 - (k - path.size()) + 1;i++){
            path.push_back(i);
            Back(k,n,i+1);
            path.pop_back();//回溯，移除路径中的最后一个数字，尝试其他可能的数字。
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        Back(k,n,1);
        return result;
    }
};

• 1.vector<vector<int>> result;：这是一个二维向量，用于存储所有有效的组合结果。

• vector<int> path;：这是一个向量，用于存储当前正在探索的数字组合。
• void Back(int k, int n, int startIndex);：这是一个递归函数，用于回溯搜索所有可能的组合。
  • k：组合中数字的数量。
  • n：目标和。
  • startIndex：本次递归搜索的起始数字。

2.Back函数中：

• if (accumulate(path.begin(), path.end(), 0) > n)：如果当前路径中的数字之和已经大于n，则停止递归，因为没有继续的必要。
• if (path.size() == k && accumulate(path.begin(), path.end(), 0) == n)：如果当前路径的长度等于k且数字之和等于n，则将当前路径添加到结果中。
• for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++)：这个循环用于迭代所有可能的数字，startIndex是当前可以开始的数字，而9 - (k - path.size()) + 1是本次递归搜索可能达到的最大数字。这是为了避免无谓的搜索，如果剩下的空间不足以容纳k-path.size()个数字，就没有必要继续了。
  • path.push_back(i);：将当前数字添加到路径中。
  • Back(k, n, i + 1);：递归调用，继续搜索下一个数字。
  • path.pop_back();：回溯，移除路径中的最后一个数字，尝试其他可能的数字。

public部分的combinationSum3方法：

• Back(k, n, 1);：启动回溯搜索过程，从数字1开始。
• return result;：返回找到的所有有效组合。

这个方法使用了回溯算法，它是一种通过探索所有可能的分支来找到所有解的算法。在每一步，它都会尝试所有可能的选择，如果当前选择导致无法达到目标，它会回溯并尝试其他选择。

17.电话号码的字母组合(回溯算法）--求组合数--只能使用一次

17.电话号码的字母组合

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

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

class Solution {
    const string letterMap[10]{
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };

    vector<string> result;
    string s;
    void Back(const string& digits,int index){
        if(s.size()==digits.size()){
            result.push_back(s);
            return;
        }
        //Dig是当前的按键号码
        int Dig=digits[index]-'0';
        //latter是按键号码映射的字符串
        string latter=letterMap[Dig];
        for(int i=0;i<latter.size();i++){
            s.push_back(latter[i]);
            Back(digits,index+1);
            s.pop_back();
        }
    }

public:
    vector<string> letterCombinations(string digits) {
        result.clear();
        s.clear();
        if(digits.size()==0){
            return result;
        }
        Back(digits,0);
        return result;
    }
};

1.vector<string> result

• const string letterMap[10]：这是一个数组，用于映射每个数字到对应的字母。例如，数字"2"映射到"abc"，数字"3"映射到"def"等。

• vector<string> result;：这是一个向量，用于存储所有可能的字母组合结果。

• string s;：这是一个字符串，用于构建当前的字母组合。

• void Back(const string& digits, int index);：这是一个递归函数，用于回溯搜索所有可能的字母组合。

  • digits：输入的数字字符串。
  • index：当前处理的数字字符串中的索引。

在Back函数中：

• if (s.size() == digits.size())：如果当前构建的字符串s的长度等于输入的数字字符串digits的长度，说明一个完整的组合已经构建完成，将其添加到结果中并返回。
• int Dig = digits[index] - '0';：获取当前索引位置的数字。
• string latter = letterMap[Dig];：获取当前数字对应的字母字符串。
• for (int i = 0; i < latter.size(); i++)：遍历当前数字对应的每个字母。
  • s.push_back(latter[i]);：将当前字母添加到字符串s中。
  • Back(digits, index + 1);：递归调用，处理下一个数字。
  • s.pop_back();：回溯，移除字符串s中的最后一个字母，尝试其他可能的字母。

2.letterCombinations方法：

• result.clear();：清除之前的结果，确保每次调用都是独立的。
• s.clear();：清除当前的字母组合。
• if (digits.size() == 0)：如果输入的数字字符串为空，则直接返回空结果。
• Back(digits, 0);：启动回溯搜索过程，从数字字符串的第一个数字开始。
• return result;：返回找到的所有字母组合。

这个方法使用了回溯算法，它是一种通过探索所有可能的分支来找到所有解的算法。在每一步，它都会尝试所有可能的选择，如果当前选择导致无法达到目标，它会回溯并尝试其他选择。

39.组合总数（回溯算法）--求组和数--可重复使用

39.组合总数

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

class Solution {
    vector<vector<int>> result;
    vector<int> path;
    void Back(vector<int>& candidates, int starIndex, int target) {
        //当前值大于目标值，直接返回
        if(accumulate(path.begin(), path.end(), 0)>target){
            return;
        }
        if (accumulate(path.begin(), path.end(), 0) == target) {
            result.push_back(path);
            return;
        }
        for (int i = starIndex; i < candidates.size(); i++) {
            path.push_back(candidates[i]);
            //输入i为组合数，输入starIndex为排列数
            Back(candidates, i, target);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        Back(candidates,0, target);
        return result;
    }
};

给定一个候选数字列表candidates和一个目标数字target，找出所有可能的组合，使得候选数字的和等于目标数字。每个数字可以在组合中重复使用。

以下是代码的详细解释：

• vector<vector<int>> result;：这是一个二维向量，用于存储所有可能的组合结果。
• vector<int> path;：这是一个向量，用于存储当前正在探索的数字组合。
• void Back(vector<int>& candidates, int starIndex, int target);：这是一个递归函数，用于回溯搜索所有可能的组合。
  • candidates：输入的候选数字列表。
  • starIndex：本次递归搜索的起始索引。
  • target：目标和。

在Back函数中：

• if (accumulate(path.begin(), path.end(), 0) > target)：如果当前路径中的数字之和已经大于target，则停止递归，因为没有继续的必要。
• if (accumulate(path.begin(), path.end(), 0) == target)：如果当前路径的数字之和等于target，则将当前路径添加到结果中。
• for (int i = starIndex; i < candidates.size(); i++)：这个循环用于迭代所有可能的数字，starIndex是当前可以开始的索引。
  • path.push_back(candidates[i]);：将当前索引处的候选数字添加到路径中。
  • Back(candidates, i, target);：递归调用，继续搜索下一个数字。
  • path.pop_back();：回溯，移除路径中的最后一个数字，尝试其他可能的数字。

public部分的combinationSum方法：

• result.clear();：清除之前的结果，确保每次调用都是独立的。
• path.clear();：清除当前的数字组合。
• Back(candidates, 0, target);：启动回溯搜索过程，从候选数字列表的第一个数字开始。
• return result;：返回找到的所有组合。

这个方法使用了回溯算法，它是一种通过探索所有可能的分支来找到所有解的算法。在每一步，它都会尝试所有可能的选择，如果当前选择导致无法达到目标，它会回溯并尝试其他选择。