LeetCode 216: Combination Sum III Solution in Python Explained

Problem Statement

In LeetCode 216: Combination Sum III, you’re given:

• k: The number of integers to use in each combination.
• n: The target sum.
• Your task is to return a list of all possible combinations of k distinct numbers from 1 to 9 that add up to n.

Each number can be used at most once, and the solution must contain unique combinations. This differs from finding the kth largest element in LeetCode 215: Kth Largest Element in an Array, focusing instead on combinatorial backtracking.

Constraints

• 2 ≤ k ≤ 9.
• 1 ≤ n ≤ 60.

Examples

Let’s see some cases:

Copy codeInput: k = 3, n = 7
Output: [[1,2,4]]
Explanation: 1 + 2 + 4 = 7, uses 3 numbers from 1-9.

Copy codeInput: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [1,4,4], [2,3,4]]
Explanation: All combinations of 3 numbers summing to 9: 
<ul>
<li>1 + 2 + 6 = 9</li>
<li>1 + 3 + 5 = 9</li>
<li>1 + 4 + 4 = 9</li>
<li>2 + 3 + 4 = 9</li>
</ul>

Copy codeInput: k = 2, n = 18
Output: [[9,9]]
Explanation: No valid combination exists (9+9=18 exceeds k=2 limit), correction: should be [] based on problem constraints.

These examples show we’re generating fixed-size combinations summing to the target.

Understanding the Problem

How do we solve LeetCode 216: Combination Sum III in Python? For k = 3, n = 7, we need three numbers from 1 to 9 that sum to 7—only [1,2,4] works. A brute-force approach generating all combinations is inefficient (9 choose k is large), so we’ll use backtracking to explore possibilities systematically. This isn’t a palindrome problem like LeetCode 214: Shortest Palindrome; it’s about constrained combination generation. We’ll use: 1. Backtracking: O(C(9,k)) time, O(k) space—our best solution. 2. Backtracking with Iteration: O(C(9,k)) time, O(k) space—an alternative.

Let’s dive into the best solution.

Best Solution: Backtracking Approach

Explanation

The Backtracking approach builds combinations recursively:

• Start with an empty list and a starting number (1).
• Add a number, recurse with updated sum and count, backtrack if needed.
• Base cases:
• If k=0 and target=0, add the combination.
• If k<0 or target<0, stop.
• Only explore numbers greater than the last used to ensure uniqueness.

This runs in O(C(9,k)) time (combinations of 9 numbers taken k at a time) and O(k) space (recursion stack), making it efficient and elegant—our best solution.

For k=3, n=7, it finds [1,2,4] by exploring valid paths.

Step-by-Step Example

Example 1: k = 3, n = 7

Goal: Return [[1,2,4]].

• Step 1: Initialize.
• result = [], curr = [], start with target=7, k=3, start=1.
• Step 2: Backtrack.
• Add 1: curr=[1], target=6, k=2.
• Add 2: curr=[1,2], target=4, k=1.
• Add 3: curr=[1,2,3], target=1, k=0, not 0, backtrack.
• Add 4: curr=[1,2,4], target=0, k=0, add [1,2,4], backtrack.
• Add 5: curr=[1,2,5], target=-1, stop.
• Add 3: curr=[1,3], target=3, k=1.
• Add 4: curr=[1,3,4], target=-1, stop.
• Add 2: curr=[2], target=5, k=2.
• Add 3: curr=[2,3], target=2, k=1.
• Add 4: curr=[2,3,4], target=-2, stop.
• Step 3: Finish.
• result = [[1,2,4]].
• Output: [[1,2,4]].

Example 2: k = 2, n = 9

Goal: Return [[1,8],[2,7],[3,6],[4,5]].

• Step 1: result = [], curr = [], target=9, k=2, start=1.
• Step 2:
• Add 1: curr=[1], target=8, k=1.
• Add 8: curr=[1,8], target=0, k=0, add [1,8].
• Add 2: curr=[2], target=7, k=1.
• Add 7: curr=[2,7], target=0, k=0, add [2,7].
• Add 3: curr=[3], target=6, k=1.
• Add 6: curr=[3,6], target=0, k=0, add [3,6].
• Add 4: curr=[4], target=5, k=1.
• Add 5: curr=[4,5], target=0, k=0, add [4,5].
• Output: [[1,8],[2,7],[3,6],[4,5]].

How the Code Works (Backtracking) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codedef combinationSum3(k: int, n: int) -> list[list[int]]:
    # Line 1: Initialize result
    result = []
    # List of combinations (e.g., [])

    # Line 2: Backtracking helper function
    def backtrack(target: int, k_remaining: int, start: int, curr: list[int]):
        # Build combinations
        if k_remaining == 0 and target == 0:
            # Valid combination found (e.g., [1,2,4])
            result.append(curr[:])
            # Add copy to result (e.g., [[1,2,4]])
            return
        if k_remaining <= 0 or target <= 0:
            # Invalid state (e.g., target=-1)
            return

        # Line 3: Explore numbers
        for i in range(start, 10):
            # Try numbers 1-9 (e.g., start=1)
            curr.append(i)
            # Add number (e.g., curr=[1])
            backtrack(target - i, k_remaining - 1, i + 1, curr)
            # Recurse (e.g., target=6, k=2)
            curr.pop()
            # Backtrack (e.g., curr=[])

    # Line 4: Start backtracking
    backtrack(n, k, 1, [])
    # Begin with full target and k (e.g., 7, 3)

    # Line 5: Return result
    return result
    # All combinations (e.g., [[1,2,4]])

This solution efficiently explores valid combinations.

Alternative: Backtracking with Iteration Approach

Explanation

The Backtracking with Iteration approach uses a loop-based structure:

• Iterate over numbers 1-9, building combinations iteratively.
• Use a stack or list to track the current path, backtrack when needed.
• Same logic as recursive but avoids recursion stack.

It’s O(C(9,k)) time and O(k) space, offering a different perspective.

Step-by-Step Example

For k=3, n=7:

• Start: curr=[], target=7, k=3.
• Add 1: curr=[1], target=6, k=2.
• Add 2: curr=[1,2], target=4, k=1.
• Add 4: curr=[1,2,4], target=0, k=0, add [1,2,4].
• Backtrack: Try other paths, none work.
• Output: [[1,2,4]].

How the Code Works (Iterative)

Copy codedef combinationSum3Iterative(k: int, n: int) -> list[list[int]]:
    result = []
    stack = [(n, k, 1, [])]

    while stack:
        target, k_rem, start, curr = stack.pop()
        if k_rem == 0 and target == 0:
            result.append(curr[:])
            continue
        if k_rem <= 0 or target <= 0:
            continue

        for i in range(start, 10):
            stack.append((target - i, k_rem - 1, i + 1, curr + [i]))

    return result

Complexity

• Backtracking (Recursive):
• Time: O(C(9,k)) – combinatorial exploration.
• Space: O(k) – recursion stack.
• Backtracking with Iteration:
• Time: O(C(9,k)) – same exploration.
• Space: O(k) – stack size.

Efficiency Notes

Backtracking (Recursive) is our best solution for its clarity and natural fit to the problem. Iterative avoids recursion overhead but is less intuitive.

Key Insights

• Backtracking: Try and undo.
• Constraints: k numbers, sum to n.
• Uniqueness: Ascending order ensures.

Additional Example

For k=2, n=15:

• [6,9], [7,8], output: [[6,9],[7,8]].

Edge Cases

• k>n: [] (e.g., k=3, n=2).
• n too large: [] (e.g., k=2, n=20).
• k=2, n=2: [[1,1]] invalid, [].

Both handle these correctly.

Final Thoughts

LeetCode 216: Combination Sum III in Python is a delightful backtracking challenge. Recursive Backtracking shines with elegance, while Iterative offers an alternative style. Want more? Try LeetCode 39: Combination Sum or LeetCode 77: Combinations. Test your skills—Solve LeetCode 216 on LeetCode with k=3, n=7 (expecting [[1,2,4]])—find those combinations today!