Combination Sum II

Leetcode 40.

find all unique combinations in candidates through pruning:

key steps:

  1. sort candidates first

  2. //pruning
    if (i != 0 && candidates[i] == candidates[i - 1] && !visited[i - 1])
    continue;

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
36
37
38
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
       List<Integer> list = new ArrayList<>();
       List<List<Integer>> ans = new ArrayList<>();
       boolean[] visited = new boolean[candidates.length];
       Arrays.sort(candidates);
       backtricking(candidates,target,ans,list,visited,0);
       
       return ans;
    }
    public void backtricking(int[] candidates,int target,List<List<Integer>> ans, List<Integer> list, boolean[] visited,int start){
      if(target <= 0){
        if(target == 0)
          ans.add(new ArrayList<>(list));    
        return;
      }

      //for loop for this layer
      for(int i = start; i < candidates.length;i++){
         if(visited[i])
           continue;
        //avoid the duplicate combinations    
        if (i != 0 && candidates[i] == candidates[i - 1] && !visited[i - 1])
            continue;

         visited[i] = true;
         target -= candidates[i];
         list.add(candidates[i]);
         //recursion 
         backtricking(candidates,target,ans,list,visited,i);
         
         //undo the previous operations
         target += candidates[i];
         visited[i] = false;
         list.remove(list.size() - 1);
      }  
    }
}