Combination Sum III

Problem in plain words

Pick exactly k different numbers from 1 to 9 so that they add up to n. Each number may be used at most once, and [1, 2, 6] counts as the same set as [6, 2, 1]. Return every such set.

For example, with k = 2 and n = 5 the answers are [1, 4] and [2, 3].

Intuition

To avoid producing the same set in different orders, only ever add numbers in increasing order: after placing a number x, the next one must be larger than x. That turns the problem into walking a decision tree where each level picks the next number, the same choose / explore / un-choose pattern as the N-Queens lesson.

Pruning keeps the tree tiny. Because the numbers increase, once the next candidate is larger than the remaining sum, every later candidate is too, so the loop can stop early.

Approach

1. Write backtrack(start, remaining, path), where start is the smallest number still allowed.
2. If path has k numbers: record a copy when remaining == 0, then return either way.
3. Otherwise loop x from start to 9. If x > remaining, break, since larger numbers cannot help.
4. Add x to path, recurse with backtrack(x + 1, remaining - x, path), then remove x.
5. Call backtrack(1, n, []) and return the results.

Dry run

Input: k = 3, n = 9.

1. Start with 1 (remaining 8). Try 2 (remaining 6): the third pick must be 6, which is allowed, so record [1, 2, 6].
2. Still under 1, try 3 (remaining 5): third pick 5 gives [1, 3, 5].
3. Try 4 under 1 (remaining 4): the third pick must exceed 4 but equal 4, impossible, and the loop breaks once candidates exceed 4.
4. Start with 2 (remaining 7), then 3 (remaining 4): third pick 4 gives [2, 3, 4].
5. Starting with 3 or more leaves no valid pair of larger numbers. Result: [[1, 2, 6], [1, 3, 5], [2, 3, 4]].

Java solution

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

    private void backtrack(int start, int k, int remaining,
                           List<Integer> path, List<List<Integer>> result) {
        if (path.size() == k) {
            if (remaining == 0) result.add(new ArrayList<>(path));
            return;
        }
        for (int x = start; x <= 9; x++) {
            if (x > remaining) break;          // larger numbers overshoot too
            path.add(x);
            backtrack(x + 1, k, remaining - x, path, result);
            path.remove(path.size() - 1);
        }
    }
}

Python solution

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []
        path = []

        def backtrack(start, remaining):
            if len(path) == k:
                if remaining == 0:
                    result.append(path[:])
                return
            for x in range(start, 10):
                if x > remaining:
                    break              # larger numbers overshoot too
                path.append(x)
                backtrack(x + 1, remaining - x)
                path.pop()

        backtrack(1, n)
        return result

Complexity

Edge cases and common mistakes

• Impossible targets: n larger than 45 (the sum of 1 to 9) or k too large for n simply produce an empty list.
• Adding `path` instead of a copy: the same list object keeps changing, so every saved answer ends up empty.
• Restarting the loop at 1: this produces duplicates like [2, 1, 6] and reuses numbers. Always start from x + 1.
• Not stopping at size `k`: without the size check the recursion keeps adding numbers past k.