Posts Combination Sum II
Post
Cancel

Combination Sum II

Problem Description

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.

leetcode

Solution

The solution is based on Combination Sum I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    
    List<List<Integer>> ans = new ArrayList<>();
    
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        
        Arrays.sort(candidates);
        
        find(candidates, 0, new ArrayList<>(), target);
        return ans;
        
    }
    
    public void find(int[] arr, int i, List<Integer> list, int target){
        
        if(target < 0) return;
        if(i == arr.length){
            if(target == 0){
                ans.add(new ArrayList<Integer>(list));    
            }
            return;
        }
        
        //Including
        list.add(arr[i]);
        find(arr, i+1, list, target-arr[i]);
        
        list.remove(list.size()-1);
        while(i<arr.length-1 && arr[i] == arr[i+1]) i++;
        
        //Excluding
        find(arr, i+1, list, target);
        
    }
}
This post is licensed under CC BY 4.0 by the author.