直接set<vector<int>>會TLE
backtracking的剪枝還是沒很熟ㄚ
這類的沒啥印象
class Solution {
public:
void helper(vector<int>& candidates, vector<vector<int>>& ans,
vector<int>& cur, int idx, int target) {
if(target == 0) {
ans.push_back(cur);
return;
}
if(idx >= candidates.size() || target<0) {
return;
}
int pre = -1;
for(int i=idx; idx<candidates.size(); idx++) {
if(candidates[idx] == pre) {
continue;
}
cur.push_back(candidates[idx]);
helper(candidates,ans,cur,idx+1,target-candidates[idx]);
cur.pop_back();
pre = candidates[idx];
}
return;
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> ans;
vector<int> cur;
helper(candidates,ans,cur,0,target);
return ans;
}
};