#216

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Combination Sum III

Find all unique combinations of k numbers adding to n using efficient backtracking with pruning in arrays.

Problem Statement

Given two integers k and n, find all unique combinations of k numbers from 1 to 9 that sum to n. Each number can be used at most once, and combinations must be unique and unordered.

Return a list of all valid combinations. The solution should use backtracking with pruning to avoid unnecessary exploration. Example: for k = 3 and n = 7, the valid output is [[1,2,4]]. Constraints: 2 <= k <= 9, 1 <= n <= 60.

Examples

Example 1

Input: k = 3, n = 7

Output: [[1,2,4]]

1 + 2 + 4 = 7 There are no other valid combinations.

Example 2

Input: k = 3, n = 9

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

1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 There are no other valid combinations.

Example 3

Input: k = 4, n = 1

Output: []

There are no valid combinations. Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

Constraints

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

Solution Approach

Recursive Backtracking

Start with an empty combination and recursively add numbers from 1 to 9. Track the remaining sum and remaining numbers needed. If the sum or count exceeds constraints, backtrack immediately.

Pruning Invalid Paths

Skip adding numbers that would exceed the remaining target sum or cause the combination length to exceed k. This prevents exploring impossible branches and reduces computation.

Recording Valid Combinations

Whenever a combination reaches exactly k numbers and sums to n, add a copy of it to the result list. Ensure each recursive call only considers numbers higher than the last added to maintain uniqueness.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the pruning efficiency but is generally O(2^9) due to subset exploration. Space complexity is O(k) for the recursion stack and temporary combination storage.

What Interviewers Usually Probe

Expect candidates to correctly implement pruning to avoid exploring impossible combinations.
Watch if recursion handles combination length and sum constraints precisely.
Check if candidates maintain uniqueness by incrementing the start number in recursion.

Common Pitfalls or Variants

Common pitfalls

Failing to prune branches early, causing unnecessary computation.
Not enforcing combination uniqueness, resulting in duplicate entries.
Incorrectly handling base cases where k numbers are not yet reached but sum cannot match n.

Follow-up variants

Allowing repeated numbers in combinations, increasing possible branches.
Finding combinations for a dynamic range instead of 1-9.
Adding a target multiple sum, e.g., all combinations summing to multiples of n.

FAQ

What is the best strategy for Combination Sum III?

Use recursive backtracking with pruning, adding numbers incrementally and skipping paths where the remaining sum cannot be reached.

How do I avoid duplicate combinations?

Ensure each recursion only considers numbers greater than the last added to maintain order and uniqueness.

Can numbers be reused in this problem?

No, each number from 1 to 9 can only be used once in each combination.

What pattern does this problem follow?

It follows a backtracking search with pruning pattern, exploring subsets while avoiding impossible branches early.

How do I know when to backtrack?

Backtrack when the current sum exceeds n, the combination length exceeds k, or when remaining numbers cannot fulfill the target sum.

terminal

Solution

Solution 1: Pruning + Backtracking (Two Approaches)

We design a function $dfs(i, s)$, which represents that we are currently enumerating the number $i$, and there are still numbers with a sum of $s$ to be enumerated. The current search path is $t$, and the answer is $ans$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def dfs(i: int, s: int):
            if s == 0:
                if len(t) == k:
                    ans.append(t[:])
                return
            if i > 9 or i > s or len(t) >= k:
                return
            t.append(i)
            dfs(i + 1, s - i)
            t.pop()
            dfs(i + 1, s)

        ans = []
        t = []
        dfs(1, n)
        return ans

Solution 2: Binary Enumeration

We can use a binary integer of length $9$ to represent the selection of numbers $1$ to $9$, where the $i$-th bit of the binary integer represents whether the number $i + 1$ is selected. If the $i$-th bit is $1$, it means that the number $i + 1$ is selected, otherwise, it means that the number $i + 1$ is not selected.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def dfs(i: int, s: int):
            if s == 0:
                if len(t) == k:
                    ans.append(t[:])
                return
            if i > 9 or i > s or len(t) >= k:
                return
            t.append(i)
            dfs(i + 1, s - i)
            t.pop()
            dfs(i + 1, s)

        ans = []
        t = []
        dfs(1, n)
        return ans

Continue Practicing

#212 word search ii #140 word break ii #90 subsets ii