Problem Description

You are given an array of distinct integers nums and a target integer target. Your task is to find the number of possible combinations from the array that add up to the target.

Key points to understand:

• You can use the same number from nums multiple times in a combination
• The order of numbers matters (different orderings count as different combinations)
• All integers in nums are distinct (no duplicates)
• The answer is guaranteed to fit in a 32-bit integer

For example, if nums = [1, 2, 3] and target = 4, the possible combinations are:

• 1 + 1 + 1 + 1
• 1 + 1 + 2
• 1 + 2 + 1
• 2 + 1 + 1
• 2 + 2
• 1 + 3
• 3 + 1

Notice that [1, 2, 1] and [2, 1, 1] are counted as different combinations because the order is different.

The solution uses dynamic programming where f[i] represents the number of ways to form sum i. Starting with f[0] = 1 (one way to make 0: use nothing), for each value from 1 to target, we check all numbers in nums. If a number x is less than or equal to the current sum i, we add f[i - x] to f[i], representing all the ways to form i - x plus the current number x.

Intuition

Think about building up to the target sum step by step. If we want to find how many ways to reach a sum of target, we can break it down into smaller subproblems.

Consider this: to reach a sum of i, we could have previously reached some smaller sum and then added one of the numbers from our array. For instance, if we want to make 5 and we have the number 2 in our array, one way is to first make 3 (in however many ways possible) and then add 2.

This leads us to a key insight: the number of ways to make sum i equals the total of:

• Number of ways to make i - nums[0] (then add nums[0])
• Number of ways to make i - nums[1] (then add nums[1])
• Number of ways to make i - nums[2] (then add nums[2])
• ... and so on for each number in the array

This is a classic dynamic programming pattern where we build solutions to larger problems from solutions to smaller ones. We start from the base case: there's exactly one way to make a sum of 0 (by choosing nothing).

For each sum from 1 to target, we look at each number x in our array. If x <= i, then we can use x as the last number in our combination. The number of ways to do this equals the number of ways to make i - x, which we've already calculated.

By building up from smaller sums to larger ones, we avoid recalculating the same subproblems repeatedly, making our solution efficient.

Solution Approach

We implement the solution using dynamic programming with a bottom-up approach. Here's how the algorithm works:

Step 1: Initialize the DP array

• Create an array f of size target + 1 where f[i] represents the number of combinations that sum to i
• Set f[0] = 1 (one way to make sum 0: choose nothing)
• Set all other values f[1] to f[target] as 0

Step 2: Fill the DP array

• For each sum i from 1 to target:
  • For each number x in nums:
    • If i >= x (we can use x in our combination):
      • Add f[i - x] to f[i]
      • This means: all ways to make i - x can be extended by adding x to make i

Step 3: Return the result

• Return f[target], which contains the total number of combinations that sum to target

Example walkthrough: Let's say nums = [1, 2, 3] and target = 4:

• Initially: f = [1, 0, 0, 0, 0]
• For i = 1: Check each number in nums
  • x = 1: f[1] += f[0] = 1
  • Result: f = [1, 1, 0, 0, 0]
• For i = 2:
  • x = 1: f[2] += f[1] = 1
  • x = 2: f[2] += f[0] = 1
  • Result: f = [1, 1, 2, 0, 0]
• For i = 3:
  • x = 1: f[3] += f[2] = 2
  • x = 2: f[3] += f[1] = 1
  • x = 3: f[3] += f[0] = 1
  • Result: f = [1, 1, 2, 4, 0]
• For i = 4:
  • x = 1: f[4] += f[3] = 4
  • x = 2: f[4] += f[2] = 2
  • x = 3: f[4] += f[1] = 1
  • Result: f = [1, 1, 2, 4, 7]

The time complexity is O(target × n) where n is the length of nums, and the space complexity is O(target) for the DP array.

Example Walkthrough

Let's walk through a small example with nums = [1, 2] and target = 3 to illustrate the solution approach.

Initial Setup:

• Create DP array: f = [0, 0, 0, 0] (indices 0 to 3)
• Set f[0] = 1 (one way to make 0)
• Result: f = [1, 0, 0, 0]

Building up each sum:

Sum = 1:

• Check x = 1: Since 1 >= 1, we can use it
  • f[1] += f[1-1] = f[0] = 1
• Check x = 2: Since 1 < 2, we can't use it
• Result: f = [1, 1, 0, 0]
• This represents: {1}

Sum = 2:

• Check x = 1: Since 2 >= 1, we can use it
  • f[2] += f[2-1] = f[1] = 1
• Check x = 2: Since 2 >= 2, we can use it
  • f[2] += f[2-2] = f[0] = 1
• Result: f = [1, 1, 2, 0]
• This represents: {1+1} and {2}

Sum = 3:

• Check x = 1: Since 3 >= 1, we can use it
  • f[3] += f[3-1] = f[2] = 2
  • This adds combinations: {1+1+1} and {2+1}
• Check x = 2: Since 3 >= 2, we can use it
  • f[3] += f[3-2] = f[1] = 1
  • This adds combination: {1+2}
• Result: f = [1, 1, 2, 3]

Final Answer: f[3] = 3

The three combinations are:

1. [1, 1, 1] - using 1 three times
2. [1, 2] - using 1 then 2
3. [2, 1] - using 2 then 1

Notice how the DP approach naturally accounts for different orderings. When we compute f[3], we consider adding 1 to all ways of making 2 (which includes both {1+1} and {2}), and separately consider adding 2 to all ways of making 1 (which is just {1}). This gives us all possible ordered combinations.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × target)

The code uses two nested loops:

• The outer loop iterates from 1 to target, which runs target times
• The inner loop iterates through all elements in nums, which runs n times (where n is the length of the array nums)
• For each combination of i and x, the operation f[i] += f[i - x] takes O(1) time

Therefore, the total time complexity is O(target × n) or O(n × target).

Space Complexity: O(target)

The code creates a single array f of size target + 1 to store the dynamic programming states. This is the only additional space used that scales with the input size. Therefore, the space complexity is O(target).

Common Pitfalls

1. Confusing with Coin Change Problem (Combinations without Order)

Pitfall: A common mistake is treating this as a standard coin change problem where order doesn't matter. Developers might iterate through nums first (outer loop) and then through the target values (inner loop), which would count [1, 2] and [2, 1] as the same combination.

Incorrect approach:

# This counts combinations where order doesn't matter
for num in nums:
    for i in range(num, target + 1):
        dp[i] += dp[i - num]

Solution: Keep the current implementation where we iterate through target values first (outer loop) and nums second (inner loop). This ensures different orderings are counted as distinct combinations.

2. Integer Overflow in Other Languages

Pitfall: While Python handles large integers automatically, in languages like Java or C++, the intermediate results might overflow even though the final answer fits in 32-bit integer.

Solution: Use appropriate data types (like long in Java) during computation and cast to int only when returning the final result:

// Java example
long[] dp = new long[target + 1];
// ... computation ...
return (int) dp[target];

3. Not Handling Edge Cases

Pitfall: Forgetting to handle edge cases like:

• Empty nums array
• target = 0
• Negative numbers in nums (which could cause infinite loops)

Solution: Add validation at the beginning:

def combinationSum4(self, nums: List[int], target: int) -> int:
    if not nums or target < 0:
        return 0
    if target == 0:
        return 1
  
    # Filter out numbers greater than target for optimization
    nums = [num for num in nums if num <= target]
    if not nums:
        return 0
  
    dp = [1] + [0] * target
    # ... rest of the code

4. Memory Optimization Missed Opportunity

Pitfall: Not recognizing when the target is very large but nums contains only small values, leading to unnecessary memory usage.

Solution: Consider using memoization with recursion for sparse cases:

def combinationSum4(self, nums: List[int], target: int) -> int:
    @lru_cache(None)
    def dfs(remaining):
        if remaining == 0:
            return 1
        if remaining < 0:
            return 0
      
        count = 0
        for num in nums:
            count += dfs(remaining - num)
        return count
  
    return dfs(target)

5. Inefficient Iteration

Pitfall: Not optimizing the inner loop by sorting nums and breaking early when a number exceeds the current sum.

Solution: Sort the array and use early termination:

nums.sort()  # Sort once at the beginning

for current_sum in range(1, target + 1):
    for num in nums:
        if num > current_sum:
            break  # No need to check larger numbers
        dp[current_sum] += dp[current_sum - num]