Combination Sum III

Leetcode 216.

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
39
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
      List<Integer> list = new ArrayList<>();
      List<List<Integer>> ans = new ArrayList<>();
      int[] nums = new int[9];
      for(int i = 1; i < 10;i++){
          nums[i-1] = i;
      }
      boolean[] visited = new boolean[nums.length]; 
      backtricking(k,n,0,list,ans,0,nums,visited);
      
      return ans;
    }
    public void backtricking(int k,int n,int depth,List<Integer> list,List<List<Integer>> ans,int start,int[] nums,boolean[] visited){
       //recursion stop condition 
       if(k == depth || n <= 0){
          if(k == depth && n == 0)
            //collect the results
            ans.add(new ArrayList<>(list));
         return;
       }
       
       //for loop for this layer
       for(int i = start;i < nums.length;i++){
         //process the nodes
         if(visited[i])
           continue;
         visited[i] = true;
         list.add(nums[i]);
         n -= nums[i];
         //recursion 
         backtricking(k,n,depth+1,list,ans,i,nums,visited);  
         //undo the previous operations
         visited[i] = false;
         list.remove(list.size() - 1);
         n += nums[i]; 
       }
    }
}