LeetCode-组合总和（C++）

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 。仅有这两种组合。

思路：本题使用回溯算法，首先定义全局变量result为结果集，path为需要保存的路径，即每一种组合，sum为路径和。

回溯函数参数为整数数组 candidates，目标值target以及起始搜索位置startIndex。

终止条件为当sum值等于target时，将path加入结果集，return。

单层搜索逻辑：for循环横向搜索，范围为从startIndex到candidates.size()，for循环内部，sum加上当前节点值，path加入当前节点，然后往深处递归，递归时，因为每一个元素可以无限次取，所以递归传入的起始搜索位置就是当前节点。然后回溯，sum减去当前节点值，path弹出当前节点值。

这里可以进行一下剪枝操作，先把candidates从小到大排序，然后递归搜索时，如果当前路径和sum大于目标值target，剩下横向搜索的其他路径也终止，具体体现在对横向搜索的范围，即i < candidates.size() && sum + candidates[i] <= target。

代码：

class Solution {	//39. 组合总和
public:
	vector<vector<int>> result;
	vector<int> path;
	int sum = 0;
	void backtracking(vector<int>& candidates, int target, int startIndex) {
		if (sum == target) {
			result.push_back(path);
			return;
		}
		for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; ++i) {
			sum += candidates[i];
			path.push_back(candidates[i]);
			backtracking(candidates, target, i);
			sum -= candidates[i];
			path.pop_back();
		}
	}

	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		sort(candidates.begin(), candidates.end());
		backtracking(candidates, target, 0);
		return result;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

参考资料：代码随想录