How do you approach Combination Sum III?

Backtrack over digits 1..9 with a start index for ascending order.

What are common mistakes on Combination Sum III?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

gitGood.dev

← Back to problems

Combination Sum III

MediumAlgorithms

Description

Find all valid combinations of k numbers that sum to n, where only digits 1 through 9 are used and each digit is used at most once.

Return the combinations with elements ascending, listed in lexicographic order. Each combination must be unique.

Example 1

Input: k = 3, n = 7

Output: [[1,2,4]]

Explanation: 1 + 2 + 4 = 7.

Example 2

Input: k = 3, n = 9

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

Explanation: Three combinations sum to 9.

Constraints

- 2 <= k <= 9 - 1 <= n <= 60

Combination Sum III: approach, complexity and pitfalls

A medium backtracking problem, graded against 8 test cases (6 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

If you are stuck

Show the 2-step hint ladder

Backtrack over digits 1..9 with a start index for ascending order.
Prune when the next digit exceeds the remaining sum.

The optimal approach

Show the approach: The approach

Bounded backtracking. Recurse over digits `start..9`, tracking the remaining sum. Stop a branch when the digit exceeds the remainder. Record a path only when it has exactly `k` digits and the remainder is 0.

Time: O(C(9,k)). Space: O(k).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.