## Finding all combinations of numbers sum up to a number (Combination Sum II)

Given a collection of candidate numbers ($C$) and a target number ($T$), find all unique combinations in $C$ where the candidate numbers sums to $T$. Each number in $C$ may only be used once in the combination.
Note:

• All numbers (including target) will be positive integers.
• Elements in a combination ($a_{1}, a_{2}, \dots ,a_{k}$) must be in non-descending order. (i.e., $a_{1} \leq a_{2} \leq \dots \leq a_{k}$).
• The solution set must not contain duplicate combinations.

INPUT: $C = {10,1,2,7,6,1,5}$ and target = 8
OUTPUT: [1, 7], [1, 2, 5], [2, 6] and [1, 1, 6]

Thoughts:
This is similar to combination sum. We just need to start from the next element in the recursion.

Code (C++):

class Solution {
public:
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
sort(num.begin(), num.end());
vector<int> partial;
vector<vector<int> > sol;
combSum2Recursion(num, target, partial, sol);
return sol;
}

void combSum2Recursion(vector<int> &num, int target, vector<int> &partial,
vector<vector<int> > &sol) {
int sum = 0;
for(int i = 0; i < partial.size(); ++i)
sum += partial[i];
if(sum == target) {
if(find(sol.begin(), sol.end(), partial) == sol.end())
sol.push_back(partial);
return;
} else if(sum > target) {
return;
} else {
for(vector<int>::iterator itr = num.begin();
itr != num.end(); ++itr) {
vector<int> partial_sol(partial);
partial_sol.push_back(*itr);
vector<int>::iterator start = itr;
vector<int> remaining(++start, num.end());
combSum2Recursion(remaining, target, partial_sol, sol);
}
}
}
};

Code (Java):
import java.util.Arrays;
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
Arrays.sort(num);
ArrayList<ArrayList<Integer>> sol = new ArrayList<ArrayList<Integer>>();
combSumRecursion(num, target, new ArrayList<Integer>(), sol);
return sol;
}

private void combSumRecursion(int[] num, int target,
ArrayList<Integer> partial, ArrayList<ArrayList<Integer>> sol) {
int sum = 0;
for(int i : partial)
sum += i;
if(sum == target) {
if(!sol.contains(partial))
return;
} else if(sum > target) {
return;
} else {
for(int i = 0; i < num.length; ++i) {
int[] remaining = new int[num.length - 1 - i];
System.arraycopy(num, i + 1, remaining, 0, remaining.length);
ArrayList<Integer> partial_sol = new ArrayList<Integer>();
combSumRecursion(remaining, target, partial_sol, sol);
}
}
}
}

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b2deb098e35c', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b2deb098e38b',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b2deb098e38d',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});