231. Combination Sum IV

Because order matters, this is really counting ordered sequences. Let dp[t] be the number of ordered ways to make t. Any such sequence ends in some num x, and removing it leaves an ordered way to make t-x — so dp[t] = sum over x of dp[t-x].

Order matters — count last steps

Since [1,2] and [2,1] count as different, define dp[t] = the number of ordered sequences from nums that sum to t. Think about the last number in such a sequence: if it is x (with x <= t), the part before it is any ordered sequence summing to t - x.

Summing over every possible last number:

dp[t] = sum of dp[t - x]  for each x in nums with x <= t

Base: dp[0] = 1 — exactly one way to make 0 (the empty sequence).

Fill dp from 1 up to target; the answer is dp[target].

Note the loop order: the outer loop is over the total t and the inner loop is over nums. That order counts permutations (order matters). Swapping the loops would count each combination once — that is the different problem (Coin Change II).

Worked example

nums = [1, 2, 3], target = 4. dp[0] = 1.

• dp[1] = dp[0] = 1 → (1)
• dp[2] = dp[1] + dp[0] = 2 → (1,1), (2)
• dp[3] = dp[2] + dp[1] + dp[0] = 4 → (1,1,1),(1,2),(2,1),(3)
• dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7

The 7 sequences: (1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2),(1,3),(3,1).

Complexity

• Time: O(target · len(nums)).
• Space: O(target).

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // dp[t] = number of ORDERED sequences from nums that sum to t.
        long[] dp = new long[target + 1];
        dp[0] = 1;
        for (int t = 1; t <= target; t++) {
            for (int x : nums) {
                if (x <= t) {
                    dp[t] += dp[t - x];
                }
            }
        }
        return (int) dp[target];
    }
}