0040 - Combination Sum II

0040 - Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Examples

Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]

Input: candidates = [2,5,2,1,2], target = 5 Output: [ [1,2,2], [5] ]

Constraints

• 1 <= candidates.length <= 100

• 1 <= candidates[i] <= 50

• 1 <= target <= 30

Java Solution (Backtracking)

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> results = new ArrayList<>();
        LinkedList<Integer> current = new LinkedList<>();
        
        Arrays.sort(candidates);
        
        backtrack(candidates, results, current, target, 0);
        return results;
    }
    
    private void backtrack(int[] candidates, List<List<Integer>> results, LinkedList<Integer> current, int remaining, int start){
        if(remaining == 0) {
            results.add(new ArrayList<>(current));
            return;
        }
        
        for(int i = start; i < candidates.length; i++) {
            if(i > start && candidates[i] == candidates[i-1]) continue;
            
            if(remaining - candidates[i] < 0) break;
            
            current.add(candidates[i]);
            backtrack(candidates, results, current, remaining - candidates[i], i+1);
            current.removeLast();
        }
    }
}