Combination Sum IV

Problem Description

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

Note that different sequences are counted as different combinations.

Examples

Constraints

• 1 ≤ nums.length ≤ 200
• 1 ≤ nums[i] ≤ 1000
• All the elements of nums are unique.
• 1 ≤ target ≤ 1000
• The answer is guaranteed to fit in a 32-bit integer.

Permutations That Sum to Target

The problem description uses the word “combinations” but details that sequence order matters (e.g. (1, 2, 1) is different from (2, 1, 1)). This means we are counting permutations of numbers that sum to target, where numbers can be reused.

Let dp[i] be the number of permutations that sum to i. To form a sum of i, the last number chosen can be any num in nums such that num ≤ i. Thus: dp[i] = sum(dp[i - num]) for all num in nums.

Initialize dp[0] = 1 (there is exactly 1 way to form a sum of 0: using an empty combination).

Solution: 1D DP

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }

        return dp[target];
    }
}

class Solution:
    def combinationSum4(self, nums: list[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1

        for i in range(1, target + 1):
            for num in nums:
                if i >= num:
                    dp[i] += dp[i - num]

        return dp[target]

#include <vector>

class Solution {
public:
    int combinationSum4(std::vector<int>& nums, int target) {
        // use unsigned to prevent intermediate overflow of dp values in C++
        std::vector<unsigned int> dp(target + 1, 0);
        dp[0] = 1;

        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }

        return dp[target];
    }
};

Complexity Analysis:

• Time Complexity: O(N * T) where N is the length of nums and T is the target. We have a nested loop of bounds T and N.
• Space Complexity: O(T) to store the DP array.

Where it breaks: in C++, intermediate values of dp[i] can temporarily overflow standard signed 32-bit integers during calculations (even if the final target answer fits). Using unsigned int prevents runtime overflow errors.

Common Mistakes

• Swapping the loops. If you put the loop over nums on the outside and the loop over target on the inside, you will count combinations instead of permutations (meaning order won’t matter, e.g. (1, 2) and (2, 1) will be counted as the same way). To count permutations, the loop over target must be on the outside.

← All Problems