We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Combination Sum IV

Number: 377

Difficulty: Medium

Paid? No

Companies: Google, Meta, TikTok, Amazon, Oracle, Snap

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. Different sequences of the same numbers count as distinct combinations.

Key Insights

  • Use dynamic programming to count the number of valid combinations.
  • The order in which numbers are picked matters, making this akin to permutation counting.
  • Initialize a DP table where dp[i] represents the number of ways to form the sum i.
  • dp[0] is initialized to 1 since there is one way to form a sum of 0 (by choosing nothing).
  • For each sum i from 1 to target, iterate over nums and update dp[i] based on dp[i - num] when i >= num.
  • For negative numbers, the problem becomes unbounded due to potential infinite combinations; hence a constraint on the combination length is required to make it well-defined.

Space and Time Complexity

Time Complexity: O(target * n), where n is the length of nums. Space Complexity: O(target), for the dp array of size target + 1.

Solution

The problem is solved using a bottom-up dynamic programming approach. We create a dp array where each dp[i] represents the number of possible combinations to reach the sum i. We iterate from 1 up to target, and for each sum, we check every number in nums. If the number can contribute to the current sum (i - num >= 0), we add the number of ways to form the remainder (i - num) to dp[i]. This ensures that every possible permutation is counted. When negative numbers are allowed in the input, the potential for an infinite number of combinations arises unless we impose additional constraints, such as limiting the length of the combination.

Code Solutions

# Python solution using dynamic programming

class Solution:
    def combinationSum4(self, nums, target):
        # Initialize dp array where dp[i] stores the number of ways to reach sum i
        dp = [0] * (target + 1)
        # Base case: there is one way to form a sum of 0 (use no elements)
        dp[0] = 1
        
        # Fill the dp table for each sum from 1 to target
        for i in range(1, target + 1):
            for num in nums:
                if i - num >= 0:
                    dp[i] += dp[i - num]
        return dp[target]
← Back to All Questions