Combination Sum IV

How it works

We can also work backwards from the target. Starting at the target, each number represents how many ways we can reach the target from that sum. When we subtract a number from the current total, we propagate the count to the resulting sum.

Steps

1. Sort the array and initialize dp[target] = 1.
2. Iterate from target down to 1.
3. For each total with a non-zero count, and for each number that does not exceed the total, add dp[total] to dp[total - num].
4. Return dp[0], which accumulates all ways to reach sum 0 starting from target.

Complexity

• Time complexity: O(n * t)
• Space complexity: O(t)

Where n is the size of the array nums and t is the given target.

Things to watch for

Confusing Combinations vs Permutations

This problem counts permutations (order matters), not combinations. [1,2,1] and [1,1,2] are counted separately. If you iterate over elements and track an index to avoid reusing earlier elements, you'll miss valid orderings.

Missing Base Case for Zero Target

Forgetting to return 1 when total == 0. This base case represents finding one valid way to form the target. Returning 0 here causes all counts to be zero.

Not Handling Negative Intermediate Results

When using bottom-up DP with a hashmap, accessing dp[total - num] when total - num is negative or doesn't exist causes errors. Always check bounds or use get() with a default value.

from typing import List
from collections import defaultdict

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        nums.sort()
        dp = defaultdict(int)
        dp[target] = 1
        for total in range(target, 0, -1):
            for num in nums:
                if total < num:
                    break
                dp[total - num] += dp[total]
        return dp[0]

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        unordered_map<int, int> dp;
        dp[target] = 1;

        for (int total = target; total > 0; total--) {
            if (dp[total] == -1) continue;
            for (auto& num : nums) {
                if (total < num) break;
                if (dp[total - num] + 0LL + dp[total] > INT_MAX) {
                    dp[total - num] = -1;
                    break;
                }
                dp[total - num] += dp[total];
            }
        }
        return dp[0];
    }
};