- tags: LeetCode
- source: https://leetcode.com/problems/combination-sum-ii/
LeetCode: 39. Combination Sum 的进阶。元素不在唯一且每一个元素只能出现一次。对结果进行排序然后通过 set 对结果进行去重：
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
backtracking(candidates, 0, 0, target);
vector<vector<int>> r;
for (auto t : res) {
r.push_back(t);
}
return r;
}
private:
set<vector<int>> res;
vector<int> track;
map<int, bool> visited;
void backtracking(vector<int>& condidates, int start, int n, int target) {
if (n == target) {
res.insert(track);
return;
}
if (n > target) {
return;
}
int c = 0;
int sz = condidates.size();
for (int i = start; i < sz; i++) {
c = condidates[i];
track.push_back(c);
backtracking(condidates, i + 1, n + c, target);
track.pop_back();
}
}
};
以下测试用例无法通过：
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
30
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
backtracking(candidates, 0, 0, target);
vector<vector<int>> r;
for (auto t : res) {
r.push_back(t);
}
return r;
}
private:
set<vector<int>> res;
vector<int> track;
map<int, bool> visited;
void backtracking(vector<int>& condidates, int start, int n, int target) {
if (n >= target) {
if (n == target) {
res.insert(track);
}
return;
}
int c = 0;
int sz = condidates.size();
for (int i = start; i < sz; i++) {
// 避免全是一样的陷入无限的循环。
if (i > start && condidates[i] == condidates[i - 1]) {
continue;
}
c = condidates[i];
track.push_back(c);
backtracking(condidates, i + 1, n + c, target);
track.pop_back();
}
cout << start << "/" << sz << ", ";
}
};