40 lines
1.4 KiB
C++
40 lines
1.4 KiB
C++
#include "s0040_combination_sum_ii.hpp"
|
||
|
||
void combinationSum2DFS(vector<int> &candidates, int target, int startIndex,
|
||
vector<int> &path, int sum, vector<bool> &used,
|
||
vector<vector<int>> &result) {
|
||
// 结束条件：总和等于 target 。不存在总和大于 target 的情况，因为已经被剪枝了
|
||
if (sum == target) {
|
||
result.push_back(path);
|
||
return;
|
||
}
|
||
|
||
// 开始迭代
|
||
int size = candidates.size();
|
||
for (int i = startIndex; i < size; ++i) {
|
||
// 剪枝，当现在节点的 sum 已经超过了 target，就没必要继续迭代了
|
||
if (sum + candidates[i] > target) break;
|
||
// 剪枝，但保留树枝重复的情况
|
||
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false)
|
||
continue;
|
||
path.push_back(candidates[i]);
|
||
used[i] = true;
|
||
combinationSum2DFS(candidates, target, i + 1, path, sum + candidates[i],
|
||
used, result);
|
||
used[i] = false;
|
||
path.pop_back();
|
||
}
|
||
}
|
||
|
||
vector<vector<int>> S0040::combinationSum2(vector<int> &candidates,
|
||
int target) {
|
||
// 对 candidates 进行升序排序，这是为了进行剪枝
|
||
sort(candidates.begin(), candidates.end());
|
||
// 初始化
|
||
vector<int> path{};
|
||
vector<vector<int>> result{};
|
||
vector<bool> used(candidates.size(), false);
|
||
combinationSum2DFS(candidates, target, 0, path, 0, used, result);
|
||
return result;
|
||
}
|