Combination Sum III LeetCode solution in Java

1
// Recursion
2

3
class Solution {
4
  public List<List<Integer>> combinationSum3(int k, int n) {
5
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
6
    // int[] arr = new int{1,2,3,4,5,6,7,8,9};
7
    List<Integer> ds = new ArrayList<>();
8
    helper(1, n, k, ds, ans);
9
    return ans;
10
  }
11

12
  private static void helper(int i, int tar, int k, List<Integer> ds, List<List<Integer>> ans) {
13
    // base
14
    if (k == 0) {
15
      if (tar == 0) {
16
        ans.add(new ArrayList<>(ds));
17
      }
18
      return;
19
    }
20
    if (tar == 0) return; // bcz if k is not zero and tar is zero then no possible valid combination
21
    if (i > tar) return;
22
    if (i > 9) return;
23

24
    // Take
25
    if (i <= tar) {
26
      ds.add(i);
27
      helper(i + 1, tar - i, k - 1, ds, ans);
28
      ds.remove(ds.size() - 1);
29
    }
30
    // Not take
31
    helper(i + 1, tar, k, ds, ans);
32

33
    return;
34
  }
35
}