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 , focusing instead on combinatorial backtracking.

Constraints

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

Examples

Let’s see some cases:

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

Input: 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>

Input: 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 ; 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:

def 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)

def 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 . Test your skills—Solve LeetCode 216 on LeetCode with k=3, n=7 (expecting [[1,2,4]])—find those combinations today!