377. Combination Sum IV

Problem Statement

link: LeetCode.cn LeetCode

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

The test cases are generated so that the answer can fit in a 32-bit integer.

Example:

Input: nums = [1,2,3], target = 4 Output: 7

Input: nums = [9], target = 3 Output: 0

Solution Approach

This solution utilizes dynamic programming to efficiently compute the number of combinations that sum up to the target integer.

Algorithm

1. Initialize a dynamic programming array dp to track the number of combinations that sum up to each value from 0 to the target.
2. Populate dp[0] with 1, indicating there’s one way to make a sum of 0 (by choosing no elements).
3. Iterate over integers from 1 to the target, updating dp[i] by summing up the number of combinations for i - n, where n is each number in the input array nums.

Implement

    class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
      #dp[i] += dp[i - n]for n in nums i <= 4
      dp = [1] + [0] * target
      for i in range(target + 1):
          for n in nums:
              if n <= i:
                  dp[i] += dp[i - n]
      return dp[target]
    
       

    
    

Twitter  facebook  Email