Combination Sum IV

• Difficulty: Medium
• Topics: Array, Dynamic Programming
• Link: https://leetcode.com/problems/combination-sum-iv/

Problem Description

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

Example 2:

Input: nums = [9], target = 3
Output: 0

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• All the elements of nums are unique.
• 1 <= target <= 1000

Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

Solution

1. Problem Deconstruction

Technical Restatement
Given a distinct integer array nums and integer target, compute the number of ordered combinations (permutation sequences) of elements from nums that sum to target. Each element can be used any number of times, and different orderings count as distinct combinations.

Beginner Explanation
Imagine you have a set of different numbers, and you want to find out how many different ways you can add these numbers together (reusing them as needed) to reach a specific total. The order in which you add them matters: for example, adding 1 then 2 is considered different from 2 then 1.

Mathematical Formulation
Let $S$ be the set of all sequences $[x_1, x_2, \dots, x_k]$ where $x_i \in \text{nums}$, $\sum_{i=1}^k x_i = \text{target}$, and $k \geq 1$. The problem requires $|S|$.

Constraint Analysis

1. Distinct elements: No duplicates in nums, simplifying memoization by avoiding overcounting identical values.
2. Target ≤ 1000: Permits dynamic programming (DP) with O(target) time/space.
3. nums[i] ≥ 1: Avoids zero/negative values, ensuring finite combinations.
4. Output ≤ 2³²-1: No need for big integers; standard integer types suffice.

Edge Cases

• Single-element nums where the element > target → 0.
• target = smallest element in nums → 1 way.
• nums contains 1, leading to many combinations (e.g., all 1s sum to target).

---

2. Intuition Scaffolding

Real-World Analogy
Climbing Stairs with Variable Steps: You can climb stairs using step sizes from nums. How many ways to reach the top (target)? Each step choice branches into new paths.

Gaming Analogy
Crafting Recipes: To craft an item requiring target points, you combine materials (nums) in any order. Each material contributes its value, and different sequences yield distinct recipes.

Math Analogy
Partition Function with Order: Count ordered integer partitions where parts are restricted to nums.

Common Pitfalls

1. Permutations vs Combinations: Mistakenly treating order as irrelevant (e.g., using subset sum logic).
2. Overcounting: Failing to recognize overlapping subproblems (e.g., recalculating counts for intermediate sums).
3. Base Case Errors: Incorrectly initializing DP[0] (should be 1, as empty combination sums to 0).
4. Ignoring Element Reuse: Assuming elements can’t be reused despite the problem allowing it.
5. Edge Case Handling: Missing cases where nums elements exceed target.

---

3. Approach Encyclopedia

Approach 1: Brute Force Recursion

• Idea: Recursively subtract each num from target until reaching 0.
• Pseudocode:

  def combinationSum4(nums, target):  
      if target == 0:  
          return 1  
      total = 0  
      for num in nums:  
          if target >= num:  
              total += combinationSum4(nums, target - num)  
      return total  
  

• Complexity: Time O(n^target) – Exponential branching. Space O(target) – Recursion depth.

Approach 2: Memoization (Top-Down DP)

• Idea: Cache results of subproblems using a memo table.
• Pseudocode:

  memo = {}  
  def dfs(t):  
      if t == 0: return 1  
      if t in memo: return memo[t]  
      res = 0  
      for num in nums:  
          if t >= num:  
              res += dfs(t - num)  
      memo[t] = res  
      return res  
  return dfs(target)  
  

• Complexity: Time O(target * n) – Each target value is computed once. Space O(target) for memo.

Approach 3: Bottom-Up DP

• Idea: Iteratively build DP table from 0 to target.
• Pseudocode:

  dp = [0] * (target + 1)  
  dp[0] = 1  
  for i in range(1, target + 1):  
      for num in nums:  
          if i >= num:  
              dp[i] += dp[i - num]  
  return dp[target]  
  

• Complexity: Time O(target * n), Space O(target).
• Visualization:

  Target: 4, nums: [1,2,3]  
  DP[0] = 1  
  DP[1] = DP[0] → 1  
  DP[2] = DP[1] + DP[0] → 1 + 1 = 2  
  DP[3] = DP[2] + DP[1] + DP[0] → 2 + 1 + 1 = 4  
  DP[4] = DP[3] + DP[2] + DP[1] → 4 + 2 + 1 = 7  
  

---

4. Code Deep Dive

Optimal Solution Code

def combinationSum4(nums, target):  
    dp = [0] * (target + 1)  
    dp[0] = 1  
    for i in range(1, target + 1):  
        for num in nums:  
            if i >= num:  
                dp[i] += dp[i - num]  
    return dp[target]  

Line-by-Line Explanation

1. dp = [0] * (target + 1): Initialize DP array to store counts for sums 0 to target.
2. dp[0] = 1: Base case – one way to sum to 0 (take nothing).
3. Loop i from 1 to target: Compute all intermediate sums up to target.
4. Loop num in nums: For each number, check if it can contribute to sum i.
5. if i >= num: Ensure we don’t access negative indices.
6. dp[i] += dp[i - num]: Add ways to reach i - num to dp[i].

Edge Case Handling

• Example 2 (nums = [9], target = 3): Since 9 > 3, the inner loop skips adding, leaving dp[3] = 0.
• nums contains 1: DP accumulates exponentially (e.g., dp[4] includes all 1s).

---

5. Complexity War Room

Hardware Considerations

• For target = 1000, the DP array uses ~4KB (1001 integers), fitting in CPU cache.
• Even with 200 nums, 1000*200 = 200,000 operations – trivial for modern CPUs.

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n^target)	O(target)	8/10	❌ Fails for target > 20
Memoization	O(target * n)	O(target)	7/10	✅ Good but stack risk
Bottom-Up DP	O(target * n)	O(target)	9/10	✅ Optimal and clear

---

6. Pro Mode Extras

Follow-Up: Negative Numbers
If nums contains negatives:

• Problem Change: Infinite loops possible (e.g., 1 and -1 can sum to 0 indefinitely).
• Solution: Restrict combination length or disallow cycles via memoization tracking steps.

Variant: Limited Combination Length
“Solve if combinations can use at most k elements”: Add a dimension to DP for current length.

Interview Cheat Sheet

• Key Insight: Order matters → Permutations, not combinations.
• First Mention: Time/space for DP is O(target * n).
• Test Cases: Check target smaller than all nums, nums containing 1, and target=0 (if allowed).