Community Problem

Combination Sum III

Difficulty: Medium

Find all unique k-digit combinations from 1-9 that sum to a target n, using cardinality-bounded backtracking.

Combination Sum III

Find all unique k-digit combinations from 1-9 that sum to a target n, using cardinality-bounded backtracking.

MEDIUM

Free

backtracking

arrays

recursion

By @tylerperry

March 16, 2026

Updated May 20, 2026

458 views

4.5 (10)

I picked this up while doing a Bloomberg loop refresh and the version that throws candidates is the one with both a SUM constraint AND a CARDINALITY constraint. Plain combination-sum lets you reuse digits and has only the sum constraint; this variant pins exactly k numbers, drawn once each from 1..9, summing to n. The catalog covered the open variant with reuse, but it skipped this fixed-cardinality cousin.

Combination Sum III

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used.
Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Examples

Example 1:

Input: k = 3, n = 7
Output: [[1, 2, 4]]
Explanation: 1 + 2 + 4 = 7. There are no other 3-digit subsets of {1..9} summing to 7.

Example 2:

Input: k = 3, n = 9
Output: [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
Explanation: All three triples sum to 9.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: The minimum 4-digit sum from {1..9} is 1 + 2 + 3 + 4 = 10, so 1 is unreachable.

Example 4:

Input: k = 9, n = 45
Output: [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
Explanation: The only 9-digit combination is the whole alphabet, summing to 1 + 2 + ... + 9 = 45.

Constraints

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

Follow-up

Why can we prune as soon as the remaining sum drops below the minimum reachable, or rises above the maximum reachable, with the digits left? With k - path.length slots remaining and only digits greater than the last picked one available, the smallest possible completion is start + (start+1) + ... + (start + remaining - 1) and the largest is 9 + 8 + ... + (10 - remaining). If n - currentSum falls outside that band, no extension can succeed, so we abort the branch.

Solution

JavaScript

Python

Hints

0/4

Hint 1

Hint 2

Hint 3

Hint 4

Solution Walkthrough

Approach: Backtracking with Sum + Cardinality Prunes (O(C(9, k)) time, O(k) space)

Maintain a current path and the remaining sum needed. At each step, pick the next digit d strictly greater than the last (to avoid permutation duplicates), push it, and recurse with remaining - d. Accept when path.length == k AND remaining == 0.

Key Insight

Two orthogonal prunes shrink the search dramatically:

Sum cutoff: if d > remaining, no further digit (which would be even larger, since we iterate ascending) can fit, so break.
Cardinality cutoff: if we have slots_left slots remaining, the next digit can be at most 9 - slots_left + 1 (so we leave room for slots_left - 1 distinct larger digits up through 9).

Algorithm

Initialize results = [], path = [].
Call backtrack(start=1, remaining=n).
In backtrack(start, remaining):
- If len(path) == k: if remaining == 0, append a copy of path. Return.
- Compute upper = 9 - (k - len(path)) + 1.
- For d from start to upper:
  
  If d > remaining, break (sum prune).
  
  Push d, recurse with (d + 1, remaining - d), pop.

Why It Works

Forcing strictly-ascending picks (start = d + 1) makes every produced combination canonical, so no two distinct recursion paths emit the same multiset. The two prunes are necessary conditions for a successful completion; if either fails, the branch cannot produce a valid combination, so cutting it preserves correctness.

Complexity

Upper bound

Text

Leaves <= C(9, k) since we choose k from 9 distinct digits
Time    O(C(9, k) * k)  (the * k is the path copy on success)
Space   O(k)            (recursion stack + path)

With k <= 9, the worst case is C(9, 4) = 126 or C(9, 5) = 126, well under 200 nodes.

Pitfalls

Iterating digits without an ascending start. Using for d in 1..9 at every level produces permutations, not combinations, so [1, 2, 4] and [2, 1, 4] would both appear.
Forgetting the cardinality cap on upper. Without it, you continue exploring digits that cannot be completed to length k.
Mutating path instead of pushing a copy. When len(path) == k && remaining == 0, append path[:] (or path.slice()); a reference to the live path would later be mutated by the backtracking pop.

Solution Code

All Problems