LeetCode-组合总和 II

40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

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

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

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

candidates需要先从小到大排序。这样方便去掉重复解集，同时也方便剪枝。

回溯函数参数为整数数组 candidates，目标值target，起始搜索位置startIndex以及一个bool类型的数组used，used用来标记同一树层的相同的元素是否使用过。

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

单层搜索逻辑：

for循环横向搜索，范围为从startIndex到candidates.size()，for循环内部，因为结果集里不能有重复解集，所以要先判断当前节点与前一节点值是否相等，并且前一节点是否使用过，如果相等并且前一节点使用过，就跳过当前节点。

然后sum加上当前节点值，path加入当前节点，used[i]标记为true，表示同一树枝candidates[i]使用过，然后往深处递归，递归时，因为每一个元素只能取一次，所以递归传入的起始搜索位置是当前节点加1，即当前节点的下一个位置。

然后回溯，used[i]标记为false，表示同一树层candidates[i]使用过，sum减去当前节点值，path弹出当前节点值。

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

代码：

class Solution {	//40. 组合总和 II
public:
	vector<vector<int>> result;
	vector<int> path;
	int sum = 0;
	void backtracking(vector<int>& candidates, int target, int startIndex, vector<bool>& used) {
		if (sum == target) {
			result.push_back(path);
			return;
		}
		for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; ++i) {
			//used[i-1]=true表示同一树枝candidates[i-1]使用过
			//used[i-1]=false表示同一树层candidates[i-1]使用过
			if (i > 0 && candidates[i] == candidates[i - 1] && used[i-1]==false)continue;
			sum += candidates[i];
			path.push_back(candidates[i]);
			used[i] = true;		//表示同一树枝candidates[i]使用过
			backtracking(candidates, target, i + 1, used);
			used[i] = false;	//表示同一树层candidates[i]使用过
			sum -= candidates[i];
			path.pop_back();
		}
	}
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
		vector<bool> used(candidates.size(), false);
		sort(candidates.begin(), candidates.end());
		backtracking(candidates, target, 0, used);
		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
26
27
28
29
30

参考资源：代码随想录