# 题目
给定一个候选人编号的集合 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] | |
] |
40. 组合总和 II - 力扣(LeetCode)
# 分析
这道题关键点在于数组去重
回溯三部曲
1 递归函数参数
vector<vector<int>> result; // 存放组合集合 | |
vector<int> path; // 符合条件的组合 | |
void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) |
2 递归终止条件
if (sum > target) { // 这个条件其实可以省略 | |
return; | |
} | |
if (sum == target) { | |
result.push_back(path); | |
return; | |
} |
3 单层逻辑
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; | |
backtracking(candidates, target, sum, i + 1, used); // 和 39. 组合总和的区别 1:这里是 i+1,每个数字在每个组合中只能使用一次 | |
used[i] = false; | |
sum -= candidates[i]; | |
path.pop_back(); | |
} |
完整代码:
class Solution { | |
private: | |
vector<vector<int>> result; | |
vector<int> path; | |
void backtracking(vector<int>& candidates, int target, int sum, 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; | |
backtracking(candidates, target, sum, i + 1, used); // 和 39. 组合总和的区别 1,这里是 i+1,每个数字在每个组合中只能使用一次 | |
used[i] = false; | |
sum -= candidates[i]; | |
path.pop_back(); | |
} | |
} | |
public: | |
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { | |
vector<bool> used(candidates.size(), false); | |
path.clear(); | |
result.clear(); | |
// 首先把给 candidates 排序,让其相同的元素都挨在一起。 | |
sort(candidates.begin(), candidates.end()); | |
backtracking(candidates, target, 0, 0, used); | |
return result; | |
} | |
}; |