Extraction based on groups of duplicates [Java]

• The solution is based on the idea from the Combination Problem I.

https://oj.leetcode.com/discuss/21655/a-recursive-yet-efficient-java-solution-with-explanation

The different part is that this time we group the duplicates and extract combinations from the groups instead of individually.

Here is the code.

``````private List<List<Integer>> res = new LinkedList<List<Integer>>();

private void combinationSum2(int[] candidates, LinkedList<Integer> vec,
int start, int target) {
// Found the combination
if(target == 0){
return;
}

for (int i = start; i < candidates.length; ++i) {
if(candidates[i] > target){
// No need to continue
break;
}else{  // candidates[i] <= target

// Find the starting point of next group
int j = i+1;
while(j < candidates.length && candidates[j] == candidates[i]){
++j;
}

if (candidates[i] < target) {
int newTarget = target;
for(int k=0; k<j-i; ++k){
// Try a new combination.
newTarget = newTarget - candidates[i];
combinationSum2(candidates, newVec, j, newTarget);
}
} else if (candidates[i] == target) {
// Found a combination
}

// start from next group
i = j-1;
}
}
}

public List<List<Integer>> combinationSum2(int[] num, int target) {
Arrays.sort(num);