LeetCode: 39. Combination Sum
- tags: LeetCode
- source: https://leetcode.com/problems/combination-sum/
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtracking(candidates, 0, target);
return res;
}
private:
vector<vector<int>> res;
vector<int> track;
void backtracking(vector<int> & candidates, int n, int target) {
if (n == target) {
res.push_back(track);
return;
}
// this is new
if (n > target) {
return;
}
for (auto c : candidates) {
track.push_back(c);
backtracking(candidates, n + c, target);
track.pop_back();
}
}
};
问题：会有不同顺序但是元素相同的数组，如何快速高效的进行过滤？
- [[2,2,3],[2,3,2],[3,2,2],[7]]
+ [[2,2,3],[7]]
一个比较 tricky 的技巧，就是判断最终结果是不是升序的，不是就放弃，居然可以通过：
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtracking(candidates, 0, target);
return res;
}
private:
vector<vector<int>> res;
vector<int> track;
void backtracking(vector<int> & candidates, int n, int target) {
if (n == target) {
int p = 0;
for (auto t : track) {
if (t < p) {
return;
}
p = t;
}
res.push_back(track);
return;
}
// this is new
if (n > target) {
return;
}
for (auto c : candidates) {
track.push_back(c);
backtracking(candidates, n + c, target);
track.pop_back();
}
}
};