combination-sum-iv.ts

/**
 * 377. Combination Sum IV  (Medium)
 * Link: https://leetcode.com/problems/combination-sum-iv/
 *
 * Given distinct integers `nums` and a `target`, return the number of possible
 * combinations that add up to target. Different orderings count as different
 * combinations (so this is really counting ordered sequences / permutations).
 *
 * Example:
 *   Input:  nums = [1, 2, 3], target = 4
 *   Output: 7            // (1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,3),(3,1),(2,2)
 *
 * Approach:
 *   1-D DP counting ordered sums. dp[t] = number of ordered ways to reach t.
 *   dp[0] = 1 (the empty sequence). For each amount t, sum dp[t - num] over all
 *   nums that fit. Iterating amount in the outer loop counts orderings (unlike
 *   the unordered coin-change-2 layout).
 *
 * Time:  O(target * nums.length)
 * Space: O(target)
 */
export function combinationSum4(nums: number[], target: number): number {
  const dp = new Array<number>(target + 1).fill(0);
  dp[0] = 1;

  for (let t = 1; t <= target; t++) {
    for (const num of nums) {
      if (num <= t) dp[t] += dp[t - num];
    }
  }

  return dp[target];
}