Leetcode 216 Combination Sum III

Analysis

If we start with ( k = 3 ) and ( n = 9 ), we need to find all possible combinations of three distinct numbers from ( 1 ) to ( 9 ) that sum up to ( 9 ).

For example, the valid combinations are:

([1, 2, 6]) → sum = 9 ✅
([1, 3, 5]) → sum = 9 ✅
([2, 3, 4]) → sum = 9 ✅

This problem is similar to the subsets problem, where we explore different combinations by picking each number one at a time. The key difference is that we need to ensure the selected numbers add up to a specific target sum.

How do we solve it?

We use backtracking!

Pseudocode:

let combinations = List<List<Integer>>;

backtracking(int num, List<Integer> current, int k, int n, int sum) {
    if sum > n return;
    if current.size > k return;
    if sum == n and current.size == k {
        combinations.add(current);
        return;
    }
    for (i = num; i <= 9; i++) {
        current.add(i);
        backtracking(i + 1, current, k, n, sum + i);
        current.pop();
    }
}

call backtracking(1, [], k, n, 0);

Explanation:

We recursively explore all possible combinations starting from num = 1.
If the sum exceeds n or the size exceeds k, we stop early (pruning).
If we find a valid combination where the sum equals n and the size equals k, we add it to our results.
We use a loop to try all numbers from num to 9, ensuring that each number appears only once in a combination.
After each recursive call, we backtrack by removing the last added number to explore other possibilities.