One minute
Leetcode 216
Combination sum III
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);
}
}