# Share my simple solution : only using 24ms and without using set to handle duplicates

• ``````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, target-num[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;
}
};``````

I wrote more than 30 OK?

I think `num[i]<target/2` is enough since elements after `num[i]` will greater `target/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:],target-candidates[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``````