[C++知识库]组合总和-回溯法

组合总和-回溯法

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。

示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]

示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

分析：回溯法模版，剪枝操作

#include "_myPrint.cpp"
using namespace std;

// 回溯法求组合问题
// 使用数字1-n之间的k个数 组合成为一个数组 是的数组的和为指定值 求出所有这样的数组 要求不重复
class Solution{
private:
    vector<vector<int>> res;
    vector<int> path;
    // 每个数组的长度  startindex控制广度搜索开始位置 target为给定目标值
    void backtracking(int k, int n, int startindex, int target){
        // 剪枝  如果在路途中已经累积超过target了 直接返回
        if (target < 0) return;
        // 返回条件
        if (path.size() == k){ // 如果搜索到了最后
            if (target == 0) res.push_back(path); // 如果和满足就加入结果集
            return;  // 无论满足不满足都要返回这一搜索路径
        }
        // 遍历 剪枝
        for (int i = startindex; i <= n - (k - path.size()) + 1; i++){
            path.push_back(i);
            // 使用target-的方式 避免重新声明一个变量sum+
            target -= i;
            // 深度迭代 从i的后一个元素开始迭代
            backtracking(k, n, i + 1, target);
            path.pop_back(); // backtrack
            target += i; // backtrack
        }
    }
public:
    vector<vector<int>> combine3(int k, int n, int target){
        res.clear();
        path.clear();
        backtracking(k, n, 1, target);
        return res;
    }

};

int main(){
    Solution s;
    vector<vector<int>> res =  s.combine3(3, 5, 9);
    printCollection p;
    p.printVecVec(res);
}