Combination Sum IV (LC 377)

Pattern: Dynamic Programming (counting orderings)
Difficulty: Medium
Key Concept: Distinct sequences count permutations: ways to reach sum t equals the sum over coins of ways to reach t - coin.

Problem Statement

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that sum to target. The difference from classic “combination sum” is that sequences that differ only by order are counted as different combinations.

You may use an element of nums an unlimited number of times.

Input: nums (positive integers, distinct), target (positive).
Output: int count (fits in 32-bit for given constraints in the problem).

Examples:

• nums = [1,2,3], target = 4 → 7 (e.g. 1+1+1+1, 1+1+2, 1+2+1, …).
• nums = [9], target = 3 → 0.

---

1. Algorithm & Pseudocode

Brute force

1. Use recursion: count(target) tries appending each x in nums if x <= target.
2. count(t) = sum over x of count(t - x), base count(0) = 1.
3. Without memoization, the same t is recomputed from many branches → exponential.

Pseudocode:

function count(t):
    if t == 0: return 1
    if t < 0: return 0
    ans = 0
    for x in nums:
        ans += count(t - x)
    return ans

Optimal

1. Use dp[s] = number of sequences summing to s.
2. dp[0] = 1.
3. For s from 1 to target: dp[s] = sum(dp[s - x]) for all x in nums with s >= x.
4. Return dp[target].

Pseudocode:

dp[0] = 1
for s from 1 to target:
    dp[s] = 0
    for x in nums:
        if s >= x: dp[s] += dp[s - x]
return dp[target]

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why this is DP, not greedy: You need all orderings; greedy choices (always take largest coin) do not count paths correctly.

Why dp[s] += dp[s - x]: Any valid sequence summing to s - x can be extended by one more number x at the end to form a distinct sequence summing to s. Summing over x counts every last-step choice.

Distinct nums: Problem assumes distinct elements; duplicates would need careful handling (not required here).

---

3. The Dry Run

nums = [1, 2], target = 3.

s	dp[s] calculation	dp[s]
0	base	1
1	dp[0] for x=1	1
2	dp[1]+dp[0] for x=1,2	1+1=2
3	dp[2]+dp[1] for x=1,2	2+1=3

Sequences: 1+1+1, 1+2, 2+1 → 3.

---

4. Java Solution

Brute Force

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        return dfs(nums, target);
    }

    private int dfs(int[] nums, int t) {
        if (t == 0) {
            return 1;
        }
        if (t < 0) {
            return 0;
        }
        int total = 0;
        for (int x : nums) {
            total += dfs(nums, t - x);
        }
        return total;
    }
}

Time: Exponential. Space: O(target) recursion depth.

Optimal

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int s = 1; s <= target; s++) {
            for (int x : nums) {
                if (s >= x) {
                    dp[s] += dp[s - x];
                }
            }
        }
        return dp[target];
    }
}

Time: O(target × n). Space: O(target).

---

5. The “Java vs. Others” Edge

• int[] dp avoids Integer boxing; overflow: problem constraints usually guarantee fit—use long if interviewer extends target.
• Order of loops (outer sum, inner coin) matches “append coin last”—swapping loops often solves coin change II (combinations without order); here order matters, so this loop order is correct.
• No HashMap needed: sums are dense 0..target.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute DFS	O(n^target) worst	O(target) stack	Recomputes same t
DFS + memo	O(target × n)	O(target)	Top-down equivalent
Bottom-up DP	O(target × n)	O(target)	Iterative, cache-friendly