LeetCode 377: Combination Sum IV Solution in Python – A Step-by-Step Guide

What Is LeetCode 377: Combination Sum IV?

LeetCode 377: Combination Sum IV provides an array of distinct positive integers (nums) and a target integer (target). Your task is to return the number of possible combinations that sum to the target, where each number in nums can be used any number of times, and order matters (permutations, not combinations). It’s a problem that tests your ability to count ordered sequences efficiently!

Problem Statement

• Input:
• nums: List of distinct positive integers.
• target: Integer representing the target sum.
• Output: Integer - Number of combinations summing to target.
• Rules:
• Each number in nums can be used unlimited times.
• Different sequences (orderings) count as distinct combinations.
• All nums are positive and distinct.

Constraints

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• 1 <= target <= 1000

Examples

• Input: nums = [1,2,3], target = 4
• Output: 7
• Combinations: [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2], [1,3], [3,1].
• Input: nums = [9], target = 3
• Output: 0
• No way to sum to 3 with only 9.
• Input: nums = [1], target = 2
• Output: 2
• [1,1] (order matters, but only one number, so 2 ways).

These show the combination count—let’s solve it!

Understanding the Problem: Counting Combinations

To tackle LeetCode 377 in Python, we need to: 1. Count all possible ordered sequences of numbers from nums that sum to target. 2. Allow unlimited use of each number. 3. Handle the order-sensitive nature (permutations).

A naive approach might generate all sequences, but that’s exponential. Instead, we’ll use:

• Best Solution: Dynamic programming—O(n * target) time, O(target) space—fast and efficient.
• Alternative Solution: Recursion with memoization—O(target * len(nums)) time, O(target) space—intuitive but slightly slower.

Let’s count with the best solution!

Best Solution: Dynamic Programming

Why This Is the Best Solution

The dynamic programming approach runs in O(n * target) time (n is len(nums)) by building a DP array where dp[i] represents the number of ways to sum to i using nums. It’s the most efficient—computing combinations bottom-up in a single pass, avoiding redundant recursive calls!

How It Works

Think of it like building sums step-by-step:

• DP Array: dp[i] = number of ways to make sum i.
• Base: dp[0] = 1 (empty sequence sums to 0).
• Update: For each sum i from 1 to target, for each num in nums, dp[i] += dp[i - num] if i ≥ num.
• Result: dp[target] is the answer.

It’s like counting ways to climb stairs with different step sizes!

Step-by-Step Example

For nums = [1,2,3], target = 4:

• Init: dp = [1, 0, 0, 0, 0] (dp[0] = 1, empty sequence).
• i=1:
• num=1: dp[1] += dp[0] = 1 (use 1).
• num=2,3: i < num, skip.
• dp = [1, 1, 0, 0, 0].
• i=2:
• num=1: dp[2] += dp[1] = 1 (1,1).
• num=2: dp[2] += dp[0] = 2 (2).
• num=3: skip.
• dp = [1, 1, 2, 0, 0].
• i=3:
• num=1: dp[3] += dp[2] = 2 (1,1,1; 1,2).
• num=2: dp[3] += dp[1] = 3 (2,1).
• num=3: dp[3] += dp[0] = 4 (3).
• dp = [1, 1, 2, 4, 0].
• i=4:
• num=1: dp[4] += dp[3] = 4 (1,1,1,1; 1,1,2; 1,2,1; 2,1,1).
• num=2: dp[4] += dp[2] = 6 (2,2; 1,1).
• num=3: dp[4] += dp[1] = 7 (3,1).
• dp = [1, 1, 2, 4, 7].
• Result: dp[4] = 7.

For nums = [9], target = 3:

• dp: [1, 0, 0, 0].
• i=1 to 3: No num ≤ i, dp = [1, 0, 0, 0].
• Result: 0.

Code with Explanation

Here’s the Python code using dynamic programming:

Copy codeclass Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # DP array: dp[i] = number of ways to sum to i
        dp = [0] * (target + 1)
        dp[0] = 1  # Base case: empty sequence sums to 0

        # Build combinations for each sum
        for i in range(1, target + 1):
            for num in nums:
                if i >= num:
                    dp[i] += dp[i - num]

        return dp[target]

Explanation

• Line 4: dp: Array of size target+1, initialized to 0.
• Line 5: dp[0] = 1 (base case: no numbers sum to 0).
• Lines 7-10: DP loop:
• For each sum i from 1 to target.
• For each num in nums, if i ≥ num, add dp[i - num] to dp[i].
• Line 12: Return dp[target].
• Time: O(n * target)—n numbers, target sums.
• Space: O(target)—DP array.

This is like summing up all paths—fast and systematic!

Alternative Solution: Recursion with Memoization

Why an Alternative Approach?

The recursive solution with memoization also runs in O(n * target) time but uses a top-down approach, computing ways to reach target by breaking it into subproblems. It’s more intuitive—great for understanding the recursive breakdown, though slightly less straightforward than bottom-up DP!

How It Works

• Recurse: Define ways(sum) as number of combinations to reach sum.
• Memoize: Cache results to avoid recomputation.
• Base: ways(0) = 1, ways(<0) = 0.
• Update: ways(sum) = sum of ways(sum - num) for each num.
• Result: ways(target).

Step-by-Step Example

For nums = [1,2,3], target = 4:

• ways(4):
• ways(3) + ways(2) + ways(1).
• ways(3):
• ways(2) + ways(1) + ways(0) = 2 + 1 + 1 = 4.
• ways(2):
• ways(1) + ways(0) = 1 + 1 = 2.
• ways(1):
• ways(0) = 1.
• ways(0): 1.
• Backtrack: ways(4) = 4 + 2 + 1 = 7.
• Result: 7.

Code with Explanation

Copy codeclass Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # Memoization cache
        memo = {}

        # Recursive helper
        def ways(remaining):
            if remaining == 0:
                return 1  # Base case: empty sequence
            if remaining < 0:
                return 0  # Invalid sum
            if remaining in memo:
                return memo[remaining]

            total = 0
            for num in nums:
                total += ways(remaining - num)
            memo[remaining] = total
            return total

        return ways(target)

Explanation

• Line 4: memo: Cache for subproblem results.
• Lines 6-19: ways:
• Base cases: remaining = 0 (1), < 0 (0).
• If cached, return memoized result.
• For each num, add ways(remaining - num).
• Cache and return total.
• Line 21: Start recursion with target.
• Time: O(n * target)—each subproblem O(n), target subproblems.
• Space: O(target)—memo dictionary.

It’s like exploring all sum paths—top-down!

Comparing the Two Solutions

• DP (Best):
• Time: O(n * target)—bottom-up.
• Space: O(target)—array.
• Pros: Fast, straightforward.
• Cons: Less intuitive process.
• Recursion with Memoization (Alternative):
• Time: O(n * target)—top-down.
• Space: O(target)—memo.
• Pros: Clear recursive logic.
• Cons: Stack overhead.

DP wins for simplicity and execution!

Additional Examples and Edge Cases

• nums=[1], target=1: 1 ([1]).
• nums=[4,2,1], target=0: 1 (empty).
• Large target: Both scale linearly.

Both handle these, DP is cleaner.

Complexity Breakdown

• DP:
• Time: O(n * target).
• Space: O(target).
• Recursion:
• Time: O(n * target).
• Space: O(target).

Both are efficient, DP is preferred.

Key Takeaways

• DP: Build sums up—fast and clean!
• Recursion: Break sums down—clear but stacked!
• Combinations: Order counts.
• Python Tip: DP rocks—see [Python Basics](/python/basics).

Final Thoughts: Count Those Combos

LeetCode 377: Combination Sum IV in Python is a counting challenge. DP is the efficiency champ, while recursion with memoization builds intuition. Want more? Try LeetCode 39: Combination Sum or LeetCode 322: Coin Change. Ready to sum? Visit Solve LeetCode 377 on LeetCode and count those combinations today!