Combination Sum III | Leetcode 216 | Optimal Solution in Python

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.

Here’s the [Problem Link] to begin with.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
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]]
Explanation:
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: []
Explanation: 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.

Optimal Approach (Smart Pruning with Running Sum)

Intuition

Instead of generating all combinations and then filtering, why not be smart about it? As we build our combination, we can keep track of the running sum. If the sum already equals our target and we have k numbers, we found a solution! If the sum exceeds our target or we have more than k numbers, we can immediately backtrack – no need to continue down that path. It’s like being a smart lottery player who stops picking numbers as soon as they see their total is already too high or they have enough numbers.

Detailed Approach

1. Track Running Sum: Pass the current sum as a parameter instead of calculating it repeatedly.
2. Early Success Detection: If sum equals n AND we have k numbers, add to result immediately.
3. Smart Pruning: If sum > n OR length > k, return immediately (early termination).
4. Avoid Duplicates: Use last parameter to ensure we only pick numbers in ascending order.
5. Efficient Backtracking: Each recursive call is O(1) since we don’t recalculate sums.

Code

class Solution:
    def func(self, n, Sum, last, nums, k, ans):
        # Base case: Found valid combination
        if Sum == n and len(nums) == k:
            ans.append(list(nums))  # Make a copy to preserve state
            return
        
        # Pruning: Early termination for invalid paths
        if Sum > n or len(nums) > k:
            return

        # Try numbers from last to 9 (ascending order, no duplicates)
        for i in range(last, 10):
            nums.append(i)
            self.func(n, Sum + i, i + 1, nums, k, ans)  # Update sum and next start
            nums.pop()  # Backtrack

    def combinationSum3(self, k, n):
        ans = []
        nums = []
        self.func(n, 0, 1, nums, k, ans)  # Start with sum=0, last=1
        return ans

Code Explanation

This optimal solution uses smart pruning to avoid unnecessary exploration. By tracking the running sum (Sum), we can immediately detect success (Sum == n and len(nums) == k) or failure (Sum > n or len(nums) > k) conditions. The last parameter ensures we only consider numbers in ascending order, preventing duplicate combinations like  and . Each recursive call updates the sum incrementally rather than recalculating it, making the operation O(1).

Dry Run

graph TD
    Root["func(n=7, Sum=0, last=1, nums=[], k=3)<br/>Find 3 numbers from 1-9 that sum to 7"]
    
    %% Level 0: try numbers 1-9
    Root --- A["Try 1<br/>nums=[1], Sum=1<br/>last=2"]
    Root --- B["Try 2<br/>nums=[2], Sum=2<br/>last=3"]
    Root --- C["Try 3<br/>nums=[3], Sum=3<br/>last=4"]
    Root --- D["Try 4<br/>nums=[4], Sum=4<br/>last=5"]
    Root --- E["Try 5,6,7,8,9<br/>Sum > 7 when k=3<br/>Pruned early"]
    
    %% Level 1 from [1]: try numbers 2-9
    A --- A1["Try 2<br/>nums=[1,2], Sum=3<br/>last=3"]
    A --- A2["Try 3<br/>nums=[1,3], Sum=4<br/>last=4"]
    A --- A3["Try 4<br/>nums=[1,4], Sum=5<br/>last=5"]
    A --- A4["Try 5<br/>nums=[1,5], Sum=6<br/>last=6"]
    A --- A5["Try 6,7,8,9<br/>Sum + min_remaining > 7<br/>Pruned"]
    
    %% Level 1 from [2]: try numbers 3-9  
    B --- B1["Try 3<br/>nums=[2,3], Sum=5<br/>last=4"]
    B --- B2["Try 4,5,6,7,8,9<br/>Sum + remaining > 7<br/>Pruned"]
    
    %% Level 1 from [3]: try numbers 4-9
    C --- C1["Try 4,5,6,7,8,9<br/>Sum + remaining > 7<br/>All pruned"]
    
    %% Level 1 from [4]: try numbers 5-9
    D --- D1["Try 5,6,7,8,9<br/>Sum already 4, need 2 more<br/>Min remaining = 5+6=11 > 3<br/>All pruned"]
    
    %% Level 2 from [1,2]: try numbers 3-9
    A1 --- A1a["Try 3<br/>nums=[1,2,3], Sum=6<br/>len=3 but Sum≠7"]
    A1 --- A1b["Try 4<br/>nums=[1,2,4], Sum=7<br/>len=3 and Sum=7"]
    A1 --- A1c["Try 5<br/>nums=[1,2,5], Sum=8<br/>Sum > 7, return"]
    A1 --- A1d["Try 6,7,8,9<br/>Sum > 7<br/>All pruned"]
    
    %% Level 2 from [1,3]: try numbers 4-9
    A2 --- A2a["Try 4<br/>nums=[1,3,4], Sum=8<br/>Sum > 7, return"]
    A2 --- A2b["Try 5,6,7,8,9<br/>Sum > 7<br/>All pruned"]
    
    %% Level 2 from [1,4]: try numbers 5-9
    A3 --- A3a["Try 5<br/>nums=[1,4,5], Sum=10<br/>Sum > 7, return"]
    A3 --- A3b["Try 6,7,8,9<br/>Sum > 7<br/>All pruned"]
    
    %% Level 2 from [1,5]: try numbers 6-9
    A4 --- A4a["Try 6<br/>nums=[1,5,6], Sum=12<br/>Sum > 7, return"]
    A4 --- A4b["Try 7,8,9<br/>Sum > 7<br/>All pruned"]
    
    %% Level 2 from [2,3]: try numbers 4-9
    B1 --- B1a["Try 4<br/>nums=[2,3,4], Sum=9<br/>Sum > 7, return"]
    B1 --- B1b["Try 5,6,7,8,9<br/>Sum > 7<br/>All pruned"]
    
    %% Results
    A1a --- Fail1["len=3 but Sum=6≠7<br/>❌ Return"]
    A1b --- Success1["len=3 and Sum=7<br/>✅ Add [1,2,4] to result"]
    A1c --- Fail2["Sum=8 > 7<br/>❌ Return (pruning)"]
    
    %% Final result
    Success1 --- Final["Final Result: [[1,2,4]]"]

    %% Styling
    style Success1 fill:#90EE90
    style Final fill:#90EE90
    
    style Fail1 fill:#DDA0DD
    style Fail2 fill:#FFB6C1
    style A2a fill:#FFB6C1
    style A3a fill:#FFB6C1
    style A4a fill:#FFB6C1
    style B1a fill:#FFB6C1
    style A1c fill:#FFB6C1
    
    style E fill:#FFE4B5
    style A5 fill:#FFE4B5
    style B2 fill:#FFE4B5
    style C1 fill:#FFE4B5
    style D1 fill:#FFE4B5
    
    style Root fill:#E6E6FA

Click here for better visualization.

Time and Space Complexity

• Time Complexity: O(C(9,k)) in worst case, but with significant pruning in practice
• Space Complexity: O(k) – Recursion depth and current combination storage

Simplifying It

This is like being a smart shopper with a budget, as you add items to your cart, you keep a running total. If you hit your budget exactly with the right number of items, perfect! If you go over budget or have too many items, you immediately put the last item back and try something else.

The optimal approach is significantly better in practice due to early pruning, even though the worst-case complexity is similar. The key optimizations are:

1. Running sum tracking – avoids recalculating sums
2. Early success detection – stops as soon as valid combination is found
3. Smart pruning – eliminates invalid paths immediately
4. Ascending order generation – prevents duplicate combinations naturally

The beauty of Combination Sum III lies in its constrained problem space (only digits 1-9) which makes the backtracking approach very efficient with proper pruning. The optimal solution demonstrates excellent backtracking principles that apply to many combinatorial problems!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.