Code Implementation

class Solution:
    def combinationSum4(self, nums, target):
        dp = [0] * (target + 1)
        dp[0] = 1
        for total in range(1, target + 1):
            for num in nums:
                if total - num >= 0:
                    dp[total] += dp[total - num]
        return dp[target]
      

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int total = 1; total <= target; ++total) {
            for (int num : nums) {
                if (total - num >= 0) {
                    dp[total] += dp[total - num];
                }
            }
        }
        return dp[target];
    }
};
      

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int total = 1; total <= target; total++) {
            for (int num : nums) {
                if (total - num >= 0) {
                    dp[total] += dp[total - num];
                }
            }
        }
        return dp[target];
    }
}
      

var combinationSum4 = function(nums, target) {
    const dp = new Array(target + 1).fill(0);
    dp[0] = 1;
    for (let total = 1; total <= target; total++) {
        for (let num of nums) {
            if (total - num >= 0) {
                dp[total] += dp[total - num];
            }
        }
    }
    return dp[target];
};
      

Problem Description

Given an array of distinct positive integers nums and a positive integer target, you are asked to find the number of possible combinations that add up to target. Each number in nums can be used an unlimited number of times in each combination, and the order of numbers in the combination matters (i.e., [1,2] and [2,1] are considered different combinations).

• All elements in nums are positive and distinct.
• You may use the same element multiple times.
• Return the total number of possible ordered combinations that sum up to target.

Thought Process

At first glance, this problem looks similar to the classic "coin change" or "subset sum" problems. One might think of generating all possible combinations recursively and counting those that sum to target. However, since the order of numbers matters, permutations (not just combinations) must be considered. This increases the number of possible solutions significantly.

A naive brute-force approach would try every possible sequence of numbers up to the target, which quickly becomes infeasible for larger inputs. To optimize, we can use dynamic programming to store and reuse results for subproblems (i.e., the number of ways to reach each intermediate sum).

The key insight is to recognize that for each total from 1 to target, we can build up the answer by considering all numbers in nums and summing the number of ways to make total - num.

Solution Approach

We'll use a bottom-up dynamic programming approach, where we build up the solution for all values from 0 to target. Here’s how we do it:

1. Initialize a DP Array:
   • Create an array dp of size target + 1, where dp[i] will store the number of ways to reach the sum i.
   • Set dp[0] = 1 because there is exactly one way to reach sum 0 (by choosing nothing).
2. Build Up the DP Array:
   • For each total from 1 to target:
   • For each number num in nums:
   • If total - num ≥ 0, add dp[total - num] to dp[total].
   • This way, we are considering all possible ways to form each total by adding each number at the end of a smaller combination.
3. Return the Result:
   • Return dp[target] as the final answer.

We use an array because we want fast, indexed access to the number of ways to reach each sum. The outer loop ensures we build up from the smallest subproblems, and the inner loop tries every number as the last element in a combination.

Example Walkthrough

Let's walk through an example with nums = [1, 2, 3] and target = 4.

• Initialization:
  • dp = [1, 0, 0, 0, 0] (dp[0]=1)
• For total = 1:
  • Try num = 1: dp[1] += dp[0] → dp[1]=1
  • Try num = 2, 3: skipped (1-2 < 0, 1-3 < 0)
  • dp = [1, 1, 0, 0, 0]
• For total = 2:
  • num = 1: dp[2] += dp[1] → 1
  • num = 2: dp[2] += dp[0] → 2
  • num = 3: skipped
  • dp = [1, 1, 2, 0, 0]
• For total = 3:
  • num = 1: dp[3] += dp[2] → 2
  • num = 2: dp[3] += dp[1] → 3
  • num = 3: dp[3] += dp[0] → 4
  • dp = [1, 1, 2, 4, 0]
• For total = 4:
  • num = 1: dp[4] += dp[3] → 4
  • num = 2: dp[4] += dp[2] → 6
  • num = 3: dp[4] += dp[1] → 7
  • dp = [1, 1, 2, 4, 7]

There are 7 different ordered combinations to sum up to 4: [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2], [1,3], [3,1].

Time and Space Complexity

• Brute-force Approach:
  • Time: Exponential, O(N^T), where N is the length of nums and T is the target, since each recursive call can branch N ways up to target depth.
  • Space: O(T) for recursion stack.
• Dynamic Programming Approach (Optimized):
  • Time: O(N × T), where N is the number of elements in nums and T is target. For each total from 1 to target, we iterate through all numbers.
  • Space: O(T), for the dp array of size target + 1.

This is a huge improvement over the brute-force method, making it feasible for larger inputs.

Summary

To solve Combination Sum IV, we use dynamic programming to efficiently count the number of ordered combinations that sum to the target. By building up from smaller subproblems and storing intermediate results, we avoid redundant work and achieve a fast, elegant solution. The key insight is treating the problem as a permutation problem (since order matters) and using a DP array to record the number of ways to reach each sum.