LeetCode 216 - Combination Sum III

This problem asks us to generate all unique combinations of exactly k distinct numbers chosen from the range 1 to 9 such that their sum equals n. Each number can only be used once in a combination. This means combinations like [1,1,5] are invalid because the number 1 is repeated.

leetcodemediumarraybacktracking

LeetCode Problem 216

Difficulty: 🟡 Medium
Topics: Array, Backtracking

Solution

Problem Understanding

This problem asks us to generate all unique combinations of exactly k distinct numbers chosen from the range 1 to 9 such that their sum equals n.

Each number can only be used once in a combination. This means combinations like [1,1,5] are invalid because the number 1 is repeated. Order also does not matter, so [1,2,4] and [4,2,1] represent the same combination and should only appear once in the output.

The input consists of two integers:

  • k, the exact number of integers we must choose
  • n, the target sum those integers must produce

The output should be a list of all valid combinations that satisfy both conditions.

For example, if k = 3 and n = 9, we need all groups of exactly three distinct numbers from 1 through 9 whose sum is 9. The valid answers are:

  • [1,2,6]
  • [1,3,5]
  • [2,3,4]

The constraints are relatively small:

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

Since the search space is tiny, this strongly suggests a backtracking or depth first search solution. There are only nine possible numbers to choose from, so exploring combinations recursively is feasible.

Several edge cases are important:

  • The target sum may be too small to be achievable. For example, k = 4 and n = 1.
  • The target sum may be too large. Even the largest four distinct digits only sum to 9+8+7+6 = 30.
  • We must avoid duplicate combinations caused by different ordering.
  • We must stop recursion early when the current sum already exceeds the target.

These observations guide us toward a recursive backtracking solution with pruning.

Approaches

Brute Force Approach

The brute force approach is to generate every possible subset of the numbers 1 through 9, then filter the subsets that:

  • contain exactly k numbers
  • sum to n

There are 2^9 = 512 subsets in total, which is actually manageable for this problem size. We could generate every subset using bitmasking or recursion, calculate its size and sum, and keep only the valid ones.

This approach is correct because every possible combination is examined exactly once.

However, it performs unnecessary work because many subsets are obviously invalid early in the process. For example:

  • subsets with too many numbers
  • subsets whose sum already exceeds n
  • subsets that cannot possibly reach n

A smarter solution avoids exploring these dead ends.

Optimal Approach, Backtracking with Pruning

The key insight is that we do not need to generate every subset completely before deciding whether it is useful.

We can build combinations incrementally using backtracking:

  • choose a number
  • recurse to choose the next number
  • stop immediately if the partial combination becomes invalid

This works well because:

  • numbers are chosen in increasing order, preventing duplicates
  • each number is used at most once
  • recursion naturally explores all valid combinations
  • pruning eliminates large parts of the search tree early

For example, if the current sum already exceeds n, there is no reason to continue exploring that path.

Similarly, if the current combination already contains more than k numbers, we stop immediately.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^9 * 9) O(9) Generates all subsets, then filters valid ones
Optimal O(C(9,k)) O(k) Backtracking explores only useful combinations

Algorithm Walkthrough

Step 1, Initialize the Result List

Create an empty list called result to store all valid combinations.

Each valid combination will be added once we find exactly k numbers whose sum equals n.

Step 2, Define the Backtracking Function

We define a recursive helper function that keeps track of:

  • the next number we are allowed to use
  • the current combination being built
  • the current sum of the combination

This recursive function explores all possible valid continuations.

Step 3, Check for a Valid Combination

At the beginning of each recursive call:

  • if the current combination has exactly k numbers
  • and the current sum equals n

then we found a valid answer.

We append a copy of the current combination to the result list.

Step 4, Prune Invalid Paths Early

If either of these conditions becomes true:

  • the current sum exceeds n
  • the combination length exceeds k

then continuing further is pointless.

We immediately return from recursion.

This pruning significantly reduces unnecessary exploration.

Step 5, Try Every Possible Next Number

Loop through all candidate numbers starting from start up to 9.

The start parameter ensures numbers are always chosen in increasing order.

For each candidate number:

  1. Add it to the current combination.
  2. Recurse with:
  • the next starting number as num + 1
  • the updated sum
  1. Remove the number afterward to backtrack.

This explores every possible valid combination exactly once.

Step 6, Return the Result

After recursion finishes, return the list of valid combinations.

Why it works

The algorithm systematically explores all combinations of distinct numbers from 1 through 9.

Because recursion always moves forward using num + 1, the same number is never reused and combinations are never generated in different orders.

Pruning guarantees we never waste time exploring impossible states.

Every valid combination is eventually constructed exactly once, so the algorithm is both complete and correct.

Python Solution

from typing import List

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

        def backtrack(start: int, current: List[int], current_sum: int) -> None:
            if len(current) == k:
                if current_sum == n:
                    result.append(current[:])
                return

            if current_sum > n:
                return

            for num in range(start, 10):
                current.append(num)

                backtrack(
                    num + 1,
                    current,
                    current_sum + num
                )

                current.pop()

        backtrack(1, [], 0)

        return result

The solution starts by creating an empty list called result that will store all valid combinations.

The backtrack function is responsible for recursively building combinations. It receives three parameters:

  • start, the next number we are allowed to use
  • current, the current combination
  • current_sum, the sum of the current combination

The first base case checks whether the combination already contains exactly k numbers. If it does, we verify whether the sum equals n. If both conditions are satisfied, we append a copy of the current combination to the result list.

The second pruning condition stops recursion if the sum already exceeds the target.

The loop iterates from start through 9, ensuring numbers are selected in strictly increasing order. This prevents duplicates and guarantees each number is used at most once.

For each candidate number:

  • we add it to the combination
  • recursively explore deeper combinations
  • remove it afterward to restore the previous state

This add-recurse-remove pattern is the standard structure of backtracking.

Finally, the algorithm begins recursion with:

  • starting number 1
  • empty combination
  • sum 0

and returns the completed result list.

Go Solution

func combinationSum3(k int, n int) [][]int {
    result := [][]int{}
    current := []int{}

    var backtrack func(start int, currentSum int)

    backtrack = func(start int, currentSum int) {
        if len(current) == k {
            if currentSum == n {
                combination := make([]int, k)
                copy(combination, current)
                result = append(result, combination)
            }
            return
        }

        if currentSum > n {
            return
        }

        for num := start; num <= 9; num++ {
            current = append(current, num)

            backtrack(num+1, currentSum+num)

            current = current[:len(current)-1]
        }
    }

    backtrack(1, 0)

    return result
}

The Go implementation follows the same recursive structure as the Python solution.

One important difference is that Go slices are references to underlying arrays. Because of this, we must create a copied slice before appending a valid combination to result. Otherwise, later modifications during backtracking would affect previously stored answers.

The line:

combination := make([]int, k)
copy(combination, current)

creates a safe independent copy.

Go also uses slice resizing syntax:

current = current[:len(current)-1]

to remove the last element during backtracking.

There are no integer overflow concerns here because all values are very small.

Worked Examples

Example 1

Input:

k = 3, n = 7

We begin with:

Step Current Combination Sum Action
1 [] 0 Start recursion
2 [1] 1 Choose 1
3 [1,2] 3 Choose 2
4 [1,2,3] 6 Not enough
5 [1,2,4] 7 Valid answer
6 [1,2,5] 8 Prune
7 [1,3] 4 Continue exploring
8 [2] 2 Continue exploring

Eventually, the only valid combination found is:

[[1,2,4]]

Example 2

Input:

k = 3, n = 9

The recursion explores combinations in increasing order.

Current Combination Sum Result
[1,2,3] 6 Continue
[1,2,4] 7 Continue
[1,2,5] 8 Continue
[1,2,6] 9 Valid
[1,3,5] 9 Valid
[2,3,4] 9 Valid

Final output:

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

Example 3

Input:

k = 4, n = 1

The smallest possible sum using four distinct positive numbers is:

1 + 2 + 3 + 4 = 10

Every recursive path exceeds the target quickly.

No valid combinations are found.

Output:

[]

Complexity Analysis

Measure Complexity Explanation
Time O(C(9,k)) Explores combinations of k numbers chosen from 1 through 9
Space O(k) Recursion stack and current combination storage

The recursion depth never exceeds k, because we stop once the combination reaches the required size.

The total number of explored states is bounded by the number of combinations formed from nine numbers. Since the input size is extremely small, this solution runs very efficiently in practice.

Test Cases

solution = Solution()

# Example 1
assert solution.combinationSum3(3, 7) == [[1, 2, 4]]

# Example 2
assert sorted(solution.combinationSum3(3, 9)) == sorted([
    [1, 2, 6],
    [1, 3, 5],
    [2, 3, 4]
])

# Example 3, impossible target
assert solution.combinationSum3(4, 1) == []

# Smallest valid k
assert solution.combinationSum3(2, 3) == [[1, 2]]

# Largest possible single valid combination
assert solution.combinationSum3(9, 45) == [[1,2,3,4,5,6,7,8,9]]

# Impossible because target too large
assert solution.combinationSum3(2, 50) == []

# Multiple valid combinations
assert sorted(solution.combinationSum3(3, 15)) == sorted([
    [1,5,9],
    [1,6,8],
    [2,4,9],
    [2,5,8],
    [2,6,7],
    [3,4,8],
    [3,5,7],
    [4,5,6]
])

# No duplicate usage allowed
assert solution.combinationSum3(3, 2) == []

# Boundary case with no solution
assert solution.combinationSum3(9, 1) == []
Test Why
k=3, n=7 Basic valid example
k=3, n=9 Multiple valid combinations
k=4, n=1 Impossible small target
k=2, n=3 Smallest meaningful solution
k=9, n=45 Uses every number exactly once
k=2, n=50 Impossible large target
k=3, n=15 Stress test with many combinations
k=3, n=2 Cannot reuse numbers
k=9, n=1 Extreme impossible boundary

Edge Cases

One important edge case occurs when the target sum is too small to be achievable. For example, k = 4 and n = 1. Even the smallest four distinct numbers sum to 10, so no valid solution exists. A naive algorithm might continue exploring unnecessarily, but the backtracking solution quickly prunes these branches once the running sum exceeds the target.

Another tricky case happens when the target sum is too large. For example, k = 2 and n = 50. Since the largest possible sum using distinct numbers from 1 through 9 is 17 for two numbers (8 + 9), no solution exists. The algorithm naturally handles this because recursion eventually exhausts all possibilities without finding a match.

A third important edge case involves preventing duplicate combinations. Without careful handling, the algorithm could generate both [1,2,6] and [2,1,6]. The implementation avoids this by always choosing future numbers from a strictly increasing range using the start parameter. This guarantees each combination is generated exactly once.

Another subtle edge case is ensuring numbers are not reused. Since recursive calls advance to num + 1, once a number is chosen it cannot appear again later in the same combination. This correctly enforces the "used at most once" requirement.