Combination Sum IV: A Dynamic Programming Solution

The "Combination Sum IV" problem is a dynamic programming challenge that focuses on finding the total number of possible combinations that add up to a given target number, using elements from an array.

Problem Statement

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

Example

• Input: nums = [1, 2, 3], target = 4 Output: 7 Explanation: The possible combination ways are:
  • (1, 1, 1, 1)
  • (1, 1, 2)
  • (1, 2, 1)
  • (1, 3)
  • (2, 1, 1)
  • (2, 2)
  • (3, 1)

Dynamic Programming Solution

function combinationSum4(nums, target) {
  let dp = new Array(target + 1).fill(0);
  dp[0] = 1;

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

  return dp[target];
}

Breaking Down the Solution

• Initialize dp Array: Create a dp array of length target + 1 and initialize it with zeros. Set dp[0] to 1, representing the base case.

• Dynamic Programming Iteration: Iterate through each possible sum from 1 to target. For each sum, iterate through the numbers in nums and add to dp[i] the number of ways to reach i - num.

• Calculate Total Combinations: By the end of the iterations, dp[target] contains the total number of ways to reach the target sum using numbers from nums.

Conclusion

The Combination Sum IV problem is a valuable exercise in dynamic programming, demonstrating how to efficiently solve problems related to counting and combinations. It illustrates the importance of building up solutions for smaller subproblems and combining them to form the solution to the overall problem.