# My solution without using set

• My idea is skip same number during recursion. Like Permutations II. Firstly sort num, then search from back for numbers sum to target.

``````vector<vector<int> > combinationSum2(vector<int> &num, int target) {
vector<vector<int>> res;
sort(num.begin(), num.end());
vector<int> cur;
find(num, target, num.size() - 1, res, cur);
return res;
}

void find(vector<int> &num, int target, int end, vector<vector<int>>& res, vector<int>& cur)
{
if (target == 0)
{
res.push_back(cur);
return;
}
if (end < 0 || num[end] * (end + 1) < target)
return;

if (num[end] <= target)
{
cur.insert(cur.begin(), num[end]);
find(num, target - num[end], end - 1, res, cur);
cur.erase(cur.begin());
}
//find combinations ends at the first number different from num[end]
int temp = num[end];
while (end >= 0 && num[end] == temp) end--;
find(num, target, end, res, cur);
}``````

• Nice code. But insertion at the beginning of a vector is expensive. If u build the result from the beginning like my code does, u can reduce the time to 24ms.

``````void comb(vector<int>& num, int st, int target, vector<int>& psol, vector<vector<int> >& result){
//processing num[st...] ,  psol: partial solution
if(target==0){
result.push_back(psol);
}else{
if( st==num.size() ) return; //cannot make it return directly
int newtarget = target - num[st];
if(newtarget>=0){
psol.push_back(num[st]);
comb(num, st+1, newtarget, psol, result);
psol.pop_back();
int i=st+1;
while( i<num.size() && num[i]==num[i-1] ) { i++; } //skip dups
comb(num, i, target, psol, result); //skip all values == num[st]

}//else cannot make it stop immediately
}

}
vector<vector<int> > combinationSum2(vector<int> &num, int target) {//O(2^n) time + O(n) space
vector<vector<int> > result;
vector<int> psol;
std::sort(num.begin(), num.end());
comb(num, 0, target, psol, result);
return result;
}``````

• Here's a Java version:

``````public class Solution {
public List<List<Integer>> combinationSum2(int[] num, int target) {
if (num == null || num.length == 0) return combos;
Arrays.sort(num);
combinationSum(num, target, new LinkedList<Integer>(), 0, combos);
return combos;
}

private void combinationSum(int[] num, int target, List<Integer> list, int start, List<List<Integer>> combos) {
if (target == 0) {
} else {
int prev = 0;
for (int i = start; i < num.length; i++) {
if (num[i] == prev) continue;
int nextTarget = target - num[i];
if (nextTarget >= 0) {
combinationSum(num, nextTarget, copy, i + 1, combos);
} else {
break;
}
prev = num[i];
}
}
}
}``````

• num[end] * (end + 1) < target

the statement above means that since num[end] is the largest number, end+1 is the number of elements. If the sum of all these elements are still less than the target, it is meaningless to continue.

• Thanks for sharing your code. My code was almost the same as yours, except
that I had used if (i>0 && num[i] == num[i-1]) continue;
if (num[i] == prev) continue;

My original code failed for test case [1,1] and target 2. Figured out the reason after reading your code. Thanks!

• my version, similar, I think I ,managed to remove some of the code in the recursive find , above the comment line, so the result looks cleaner

``````public class Solution {
List<Integer> partialSolution ;
List<List<Integer>> result = new  ArrayList<List<Integer>>();
public List<List<Integer>> combinationSum2(int[] num, int target) {
partialSolution = new ArrayList<Integer>();
Arrays.sort(num);

recursive(num,0, target);

return new ArrayList<List<Integer>>(result);
}

private void recursive(int[] candidates,int low, int target) {
if ( target == 0) {
List<Integer> elem = new ArrayList<Integer>(partialSolution);
return;
} else if ( target < 0) {
return;
}

for(int i=low;i<candidates.length;i++) {
if (i > low && candidates[i] == candidates[i-1]) continue;