Dynamic Programming
13. Combination Sum IV

Combination Sum IV (opens in a new tab) Medium

Problem

Given an integer array nums with all positive integers and an integer target, find 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)
  2. (1, 1, 2)
  3. (1, 2, 1)
  4. (1, 3)
  5. (2, 1, 1)
  6. (2, 2)
  7. (3, 1)

Summary

To solve this problem, we can use dynamic programming to find the number of possible combinations for each possible sum from 1 to target. We will iterate through the nums array, and for each number, we update the number of possible combinations for each sum in the DP array.

Solution

In TypeScript

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

In Python

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 >= 0:
				dp[i] += dp[i - num]
 
	return dp[target]

Step-by-step explanation

The approach implemented in the steps above is based on dynamic programming, and it's designed to solve the "Combination Sum IV" problem efficiently by avoiding redundant calculations. The main idea behind this implementation is to build an array dp that stores the number of possible combinations for each sum up to the target.

  1. First, we create a 1D dynamic programming array dp of length target + 1, initializing all its elements to 0. The purpose of this array is to store the number of possible combinations for each sum up to the target. We initialize dp[0] to 1, because there is one way to achieve a sum of 0: not using any numbers.

    The problem asks for the number of possible combinations that add up to the target, and using dynamic programming allows us to build this result incrementally. By calculating the number of combinations for smaller sums first and using these intermediate results, we can efficiently find the final answer without recalculating combinations for the same sum repeatedly.

const dp: number[] = Array(target + 1).fill(0);
dp[0] = 1;

  1. We then iterate through all possible sums from 1 to target, inclusive. In each iteration, we use a nested loop to iterate through the nums array.

    In the implementation, we iterate through all possible sums from 1 to target (inclusive) and use a nested loop to consider each number in the nums array. This allows us to evaluate all potential combinations that can be formed using the numbers in the nums array for each sum.

for (let i = 1; i <= target; i++) {
	for (const num of nums) {
		// ...
	}
}

  1. Inside the nested loop, we check if the current sum i minus the current number num is greater than or equal to 0. This check ensures that we only use valid numbers from the nums array to create the sum i.

    By checking if the current sum i minus the current number num is greater than or equal to 0, we ensure that we only use valid numbers from the nums array to create the sum i. This condition helps us to avoid using negative numbers or numbers greater than the target, which would be invalid in forming the combinations.

if (i - num >= 0) {
	// ...
}

  1. If the condition is satisfied, we add the number of possible combinations for the sum i - num to the number of possible combinations for the sum i. This step effectively computes the number of combinations for each sum by considering all the possible numbers from the nums array that can be added to a smaller sum to reach the current sum i.

    The key idea in this implementation is updating the dp array by adding the number of possible combinations for the sum i - num to the number of possible combinations for the sum i. This step accounts for all the possible ways that the current number num can be added to a smaller sum to reach the current sum i. By doing this, we effectively compute the number of combinations for each sum by considering all the possible numbers from the nums array that can be used.

dp[i] += dp[i - num];

  1. After iterating through all possible sums and updating the dp array, we return the value at dp[target], which represents the total number of possible combinations that add up to the target sum.

    Finally, after iterating through all possible sums and updating the dp array, we return the value at dp[target], which represents the total number of possible combinations that add up to the target sum. This is the final result we want for the problem.

return dp[target];

Complexity Analysis

Time Complexity

The time complexity of this solution is O(target * n), where n is the length of the input array nums. We iterate through the DP array of length target + 1 for each number in the nums array.

Space Complexity

The space complexity of this solution is O(target), as we use a 1D array to store the number of possible combinations for each sum up to the target.

12. Decode Ways