class Solution {
public:
vector<vector<int>> res;
void go(int startpos, vector<int>oneres, vector<int> &num, int target)
{
for (int i = startpos; i < num.size(); i++)
{
if(num[i]<target)
{
oneres.push_back(num[i]);
// In question"Combination Sum", here should be i instead of i+1, cuz it allow
// using one number more than once
go(i + 1, oneres, num, targetnum[i]);
oneres.pop_back();
}
else if(num[i]==target)
{
oneres.push_back(num[i]);
res.push_back(oneres);
oneres.pop_back();
return;
}
else
{
return;
}
// handle duplicates
while (i < num.size()  1 && num[i] == num[i + 1])
i++;
}
}
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
sort(num.begin(), num.end());
vector<int>oneres;
go(0, oneres, num, target);
return res;
}
};
Share my simple solution : only using 24ms and without using set to handle duplicates


Why keep showing: Please provide more information  at least 30 characters
I wrote more than 30 OK?I think
num[i]<target/2
is enough since elements afternum[i]
will greatertarget/2
which will definitely exceed the target in the next recursion.I use a variable to store the last number, which used to handle duplication. However your method share the same thought but less comparisons than mine.
Good Job!
Here's my AC python solution:
class Solution: # @param candidates, a list of integers # @param target, integer # @return a list of lists of integers def combinationSum2(self, candidates, target): def combinationSum(candidates,target,combination,ret): length = len(candidates) if length == 0 or candidates[0]>target: return last = None for i in range(length): if candidates[i] <= target/2 and candidates[i] != last: combinationSum(candidates[i+1:],targetcandidates[i],combination+[candidates[i]],ret) elif candidates[i] == target and candidates[i] != last: ret.append(combination+[candidates[i]]) else: continue last = candidates[i] ret = [] combinationSum(sorted(candidates),target,[],ret) return ret