Return the number of ordered combinations of numbers from nums (with repetition) that add up to target. Different orders count separately.
dp[s] = number of ordered sequences summing to s. dp[s] += dp[s − x] for every x. The sum is the outer loop, so order matters.
1function combinationSum4(nums: number[], target: number): number {2const dp = new Array(target + 1).fill(0);3dp[0] = 1;4for (let s = 1; s <= target; s++)5for (const x of nums)6if (x <= s) dp[s] += dp[s - x];7return dp[target];8}
dp[0] = 1 (the empty sequence).
Space: play/pause · ←/→: step