Combination Sum IV
Problem
Given an array of distinct positive integers and a target, return the number of ordered tuples whose values sum to target. You may reuse each value any number of times.
nums = [1, 2, 3], target = 47def combination_sum4(nums, target):
dp = [0] * (target + 1)
dp[0] = 1
for t in range(1, target + 1):
for num in nums:
if num <= t:
dp[t] += dp[t - num]
return dp[target]function combinationSum4(nums, target) {
const dp = new Array(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];
}class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int t = 1; t <= target; t++)
for (int num : nums)
if (num <= t) dp[t] += dp[t - num];
return dp[target];
}
}int combinationSum4(vector<int>& nums, int target) {
vector<unsigned int> dp(target + 1, 0);
dp[0] = 1;
for (int t = 1; t <= target; t++)
for (int num : nums)
if (num <= t) dp[t] += dp[t - num];
return dp[target];
}Explanation
This problem counts ordered tuples, so 1+3 and 3+1 count as two different answers. That ordering hint is exactly why we loop differently from the "combinations" version: here the amount is the outer loop and the numbers are the inner loop.
dp[t] = how many ordered tuples sum to t. We seed dp[0] = 1 for the empty tuple, which is the one way to make 0.
For each target value t from 1 up, we consider which number was placed last. If that last number is num (and num <= t), the rest must form t - num in any order, which we already counted as dp[t - num]. Summing over every num gives dp[t] += dp[t - num].
Because the "last picked number" can be any value, every ordering is counted once, which is what we want.
Example: nums = [1, 2, 3], target = 4. Working up the table gives dp[4] = 7, matching the seven ordered ways to reach 4.