难度参考

        难度：困难

        分类：回溯算法

        难度与分类由我所参与的培训课程提供，但需 要注意的是，难度与分类仅供参考。且所在课程未提供测试平台，故实现代码主要为自行测试的那种，以下内容均为个人笔记，旨在督促自己认真学习。

题目

        给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合，candidates中的数字可以无限制重复被选取。

        说明：

        所有数字（包括target）都是正整数。

        解集不能包含重复的组合。

        示例1:

        输入:candidates =[2，3，6，7]，target = 7,

        所求解集为：［[7]，[2，2，3]］

        示例2:

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

        所求解集为：[[2，2，2，2]，[2，3，3]，[3，5]]

思路

        这个问题是一个典型的组合求和问题，可以通过回溯算法来解决。回溯算法基于试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其他的可能的分步解答再次尝试寻找问题的答案。

        对于这个特定问题，我们可以按照以下步骤来设计我们的算法：

        理解问题

给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。candidates中的数字可以无限制重复被选取。需要注意的是，解集不能包含重复的组合。

        设计策略

        排序（可选）：首先，可以对candidates数组进行排序。这一步是可选的，但有助于优化，因为它可以让我们在某些情况下提前终止搜索。
回溯：使用回溯的方法来逐步构建组合，并且当组合的和等于目标值target时，将其添加到结果集中。
        选择路径：从candidates的开始，逐个尝试数组中的每个数，将其加入到当前组合中，并递归地调用回溯函数，继续尝试下一个数。每次递归调用时，目标值target减去当前选择的数。
撤销选择：如果当前组合的和大于target，或者已经找到一个有效的组合，就回溯，撤销最后的选择，尝试下一个数。
        实现细节

        使用一个辅助函数backtrack来进行回溯搜索。这个函数接受当前的组合combination，当前的开始搜索位置start，和当前的目标值target作为参数。
        当target减到0时，说明找到了一个有效的组合，将其添加到结果集中。
        对于candidates中的每个数，如果它不大于当前的target，就尝试将它加入到当前组合中，并递归地调用backtrack，同时将target减去这个数。每次递归调用后，需要撤销上一步的选择，以便尝试其他的数。
        通过这种方式，我们可以遍历所有可能的组合，找到所有和为target的组合。

示例

        假设我们有一个数组candidates = [2, 3, 6, 7]和一个目标数target = 7，我们需要找到所有组合，使得组合中数字的和为7。

        初始条件

        candidates = [2, 3, 6, 7]
        target = 7
        解决步骤

        开始搜索：

        从数组的第一个元素开始，即数字2。
        尝试数字2：
        将2加入到当前组合中，组合变为[2]，target更新为7-2=5。
        再次尝试2，组合变为[2, 2]，target更新为5-2=3。
        再次尝试2，组合变为[2, 2, 2]，target更新为3-2=1。此时，再加2已经超过目标值，尝试下一个数字。
        尝试数字3：
        从组合[2, 2]开始，尝试加入3，组合变为[2, 2, 3]，target更新为3-3=0。
        发现一个有效组合[2, 2, 3]，因为它们的和等于原始target7。
        回溯到组合[2]，尝试下一个数字。
        尝试数字3：
        从组合[2]开始，尝试加入3，组合变为[2, 3]，target更新为5-3=2。
        此时再加3已经超过目标值，尝试下一个数字。
        尝试数字6：
        从组合[2]开始，尝试加入6，但发现2+6已经超过目标值7，因此不再继续尝试。
        尝试数字7：
        从空组合开始，尝试加入7，组合变为[7]，target更新为7-7=0。
        发现一个有效组合[7]。
        搜索结束：最终找到的有效组合有[2, 2, 3]和[7]。
        结果

        有效组合1：[2, 2, 3]
        有效组合2：[7]

梳理

        回溯算法的核心在于尝试与撤销的过程，通过这种方式来遍历问题的所有可能解。在上述例子中，我们使用回溯算法来寻找所有和为特定target的组合。这一过程体现在以下几个方面：

        我们从candidates数组的开始尝试每一个数，将其加入到当前的组合中，并更新剩余的target（即target减去当前数的值）。这一步骤相当于在决策树上向下走一步。

        在加入一个数到组合后，我们递归地调用相同的函数来处理更新后的target和当前组合。这一过程相当于在探索决策树的一个分支，直到找到解或者该分支无法继续向下探索（即当前组合的和超过了target）。

        当我们发现当前的组合无法满足条件（和超过target）或者我们已经找到了一个有效的组合，我们需要撤销最后的选择（即从当前组合中移除最后加入的数），然后尝试下一个数。这相当于在决策树上回到上一个节点，并探索另一个分支。

        在上述例子中，当我们尝试组合[2, 2]并继续加入2时，发现和变为6，仍然小于target7。我们再次尝试加入2，此时和变为8，超过了target。于是，我们撤销最后一次加入2的操作，回到和为6的状态（即组合[2, 2]），然后尝试加入3。这个撤销操作就是回溯的体现，它让我们能够回到之前的状态，尝试其他可能的数，直到找到所有满足条件的组合。

        通过这种方式，回溯算法能够系统地探索所有可能的组合，直到找到所有满足条件的解。每当遇到一个死路，算法就会回溯到上一个节点，尝试其他的路径。这种策略确保了算法能够覆盖到决策树的每一个节点，从而找到所有可能的解。

代码

#include <vector> // 包含 vector 头文件
#include <iostream> // 包含输入输出流头文件
#include <algorithm> // 包含算法头文件

using namespace std; // 使用标准命名空间

void backtrack(vector<int>& candidates, int target, vector<vector<int>>& res, vector<int>& combination, int start) {
if (target == 0) { // 如果目标值为0，找到一个有效的组合
res.push_back(combination); // 将组合添加到结果中
return; // 结束此次递归
}

for (int i = start; i < candidates.size() && target >= candidates[i]; ++i) {
    combination.push_back(candidates[i]);  // 选择当前数字
    backtrack(candidates, target - candidates[i], res, combination, i);  // 继续探索
    combination.pop_back();  // 撤销选择
}
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res; // 存储结果的二维向量
vector<int> combination; // 存储单个组合的一维向量
sort(candidates.begin(), candidates.end()); // 先对候选数字进行排序，有助于提前终止无效的探索
backtrack(candidates, target, res, combination, 0); // 调用回溯函数进行组合求解
return res; // 返回结果
}

int main() {
vector<int> candidates1 = {2, 3, 6, 7}; // 候选数字序列
int target1 = 7; // 目标和
vector<vector<int>> res1 = combinationSum(candidates1, target1); // 调用组合求解函数得到结果
cout << “Example 1:” << endl;
for (const auto& combination : res1) { // 遍历每一个组合
for (int num : combination) { // 遍历组合中的每一个数字
cout << num << " "; // 输出数字
}
cout << endl; // 换行
}

vector<int> candidates2 = {2, 3, 5};  // 候选数字序列
int target2 = 8;  // 目标和
vector<vector<int>> res2 = combinationSum(candidates2, target2);  // 调用组合求解函数得到结果
cout << "Example 2:" << endl;
for (const auto& combination : res2) {  // 遍历每一个组合
    for (int num : combination) {  // 遍历组合中的每一个数字
        cout << num << " ";  // 输出数字
    }
    cout << endl;  // 换行
}

return 0;
}

        时间复杂度：0(2^n），n是数组candidates的长度。

        空间复杂度：o(target)

打卡