Combination Sum III

Head on over here to try the problem for yourself.

Another permutation based problem solved using back-tracking.

Algorithm

The goal is to get all combinations (without repeat) of k integers from 1-9 whose sum is n. To achieve this, simply backtrack and decrement n with the current integer. Also, to ensure no repeats, pass in the next integer to the recursive call.

Code

public List<List<Integer>> combinationSum3(int k, int n) {
  List<List<Integer>> result = new ArrayList<>();
  helper(result, new ArrayList<>(), k, n, 1);
  return result;
}

public void helper(List<List<Integer>> result, List<Integer> curr, int k, int n, int index) {
  if(n < 0) return;
  if(n == 0 && curr.size() == k) {
    result.append(new ArrayList<>(curr));
    return;
  }

  for(; index < 10; index++) {
    // here i had to first append then pass curr
    // because curr.add() returns boolean
    curr.add(index);
    helper(result, curr, k, n - index, index + 1);
    // delete previous element to continue in 
    // for loop
    curr.remove(curr.size() - 1);
  }
}