[LeetCode] Problem 216 - Combination Sum III

Posted on | In ,

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note

  • All numbers will be positive integers.
  • The solution set must not contain duplicate combinations.

Example

No.1

Input: k = 3, n = 7

Output: [[1,2,4]]

No.2

Input: k = 3, n = 9

Output: [[1,2,6], [1,3,5], [2,3,4]]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> combination = new ArrayList<>();

    combinationSum3Helper(result, combination, k, n, 1);

    return result;
}

private void combinationSum3Helper(List<List<Integer>> result, List<Integer> combination, int k, int n, int idx) {
    if (n == 0 && combination.size() == k) {
        result.add(new ArrayList<>(combination));
        return;
    }

    for (int i = idx; i <= 9 && combination.size() < k && n > 0; i++) {
        combination.add(i);
        combinationSum3Helper(result, combination, k, n - i, i + 1);
        combination.remove(combination.size() - 1);
    }
}