We need to pick exactly k distinct numbers from the set {1, 2, 3, 4, 5, 6, 7, 8, 9} such that they add up to n. The order doesn't matter, so [1, 2, 4] and [2, 1, 4] count as the same combination.

What makes this different from other combination-sum problems is the fixed candidate set. We always work with the digits 1 through 9, and each digit can appear at most once, so there are only 2^9 = 512 possible subsets. Even a brute-force approach that checks every subset is fast enough.

Because order does not matter, we build each combination in increasing order. That single rule produces every combination exactly once and never generates a reordering of one we already have.

Key Constraints:

Intuition

With only 512 subsets of {1, 2, ..., 9}, we can generate every one of them and keep the subsets that have exactly k elements and sum to n.

To generate all subsets recursively, walk through the numbers 1 to 9 and, for each one, branch twice: include it or skip it. After a decision has been made for all 9 numbers, check whether the resulting subset meets both criteria.

This version does no pruning. It generates all 512 subsets and checks each one at the end, which the constraints make fast enough.

Algorithm

Example Walkthrough

Input: k = 2, n = 7

The recursion makes an include-or-skip decision for each digit from 1 to 9, producing 512 leaves. Take one path as an example: include 1, skip 2 through 5, include 6, skip 7 through 9. At the leaf, the subset {1, 6} has exactly 2 elements and the remaining target is 7 - 1 - 6 = 0, so it goes into the result. Across all 512 leaves, exactly three subsets pass both checks:

Every other subset fails the size check or the sum check, so the returned result is [[1, 6], [2, 5], [3, 4]].

Code

This approach commits to all 512 subsets before checking anything. The next approach checks constraints while building and cuts off branches that can no longer succeed.

Intuition

The brute force evaluates a subset only after all 9 include-or-skip choices are made. Backtracking checks constraints as it goes: it builds combinations one number at a time, in increasing order, and stops extending a partial combination as soon as nothing valid can come from it.

A branch ends in one of three ways:

Picking numbers in increasing order (after picking 3, the next try is 4 or higher) also guarantees each combination is generated exactly once, never as a reordering of an earlier one.

Algorithm

Example Walkthrough

Input: k = 3, n = 7

The first view tracks which candidates get picked or pruned. The second view shows the combination being built and unbuilt as the search backtracks.

Code

Backtracking solves the problem with recursion. The search space is small enough that a single loop over bitmasks can replace the recursion entirely.

Intuition

Since we choose from exactly 9 numbers, any subset can be represented as a 9-bit integer. Bit 0 records whether the number 1 is included, bit 1 stands for the number 2, and so on up to bit 8 for the number 9. The bitmask 0b000010110 (decimal 22) has bits 1, 2, and 4 set, so it represents the subset {2, 3, 5}.

Instead of building combinations recursively, iterate through all integers from 0 to 511 (2^9 - 1). For each integer, check two things: does it have exactly k bits set (meaning k numbers chosen), and do the corresponding numbers sum to n? If both conditions hold, extract the combination and add it to the result.

There is no recursion to manage and no backtracking state to undo. The approach works because the search space is small enough to enumerate exhaustively; with a larger candidate set, checking 2^N masks would not be practical.

Algorithm

Example Walkthrough

Input: k = 2, n = 7

Masks are checked in increasing numeric order, so the matches arrive as [3, 4] (mask 12), then [2, 5] (mask 18), then [1, 6] (mask 33).

Code