NUHMAN.com

📘 Problem Statement

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

Example:

python

Input: nums = [1, 2, 3], target = 4
Output: 7
Explanation:
    The possible combinations are:
    1 + 1 + 1 + 1 = 4
    1 + 1 + 2 = 4
    1 + 2 + 1 = 4
    2 + 1 + 1 = 4
    2 + 2 = 4
    1 + 3 = 4
    3 + 1 = 4

You may assume that the solution can be computed in a reasonable amount of time for inputs with target ≤ 1000.

🧠 Key Insight

This problem can be solved using dynamic programming (DP). The idea is to compute the number of ways to reach a target sum for each possible intermediate sum (from 0 to target). We can approach it by building up the solution using smaller subproblems.

Steps:

1. Dynamic Programming Array: Let dp[i] represent the number of ways to sum up to i using the numbers in the nums array.
2. Base Case: dp[0] = 1, because there is one way to sum up to 0 — by choosing no numbers.
3. Transition: For each target sum i (from 1 to target), compute the number of ways to reach it by iterating through all numbers in nums and adding the ways to reach i - num.
4. Final Answer: The value of dp[target] will give us the number of ways to reach the target sum.

💡 Approach

1. Initialize DP Table: We initialize a dp array of size target + 1 where each index i will store the number of combinations that add up to i.
2. Base Case: dp[0] = 1 because there is exactly one way to sum up to 0 (use no numbers).
3. Fill DP Array: For each number i from 1 to target, iterate through each number in nums and update the number of ways to form the sum i by adding the ways to form i - num for each number num in nums.

🐍 Python Code

python

class Solution:
    def combinationSum4(self, nums: list[int], target: int) -> int:
        # Initialize dp array with zeros
        dp = [0] * (target + 1)
        # Base case: there's one way to make 0 (by choosing nothing)
        dp[0] = 1
        
        # Iterate through all targets from 1 to the given target
        for i in range(1, target + 1):
            for num in nums:
                if i - num >= 0:  # Only consider valid subproblems
                    dp[i] += dp[i - num]  # Add combinations from previous subproblem
        
        return dp[target]

🔍 Step-by-Step Explanation

1. Initialization of DP Array

python

dp = [0] * (target + 1)
dp[0] = 1

• We create a list dp of size target + 1 initialized with zeros.
• dp[0] is set to 1 because there is exactly one way to achieve the target sum of 0: by choosing no numbers.

2. Filling the DP Array

python

for i in range(1, target + 1):
    for num in nums:
        if i - num >= 0:
            dp[i] += dp[i - num]

• We iterate through all possible target values from 1 to target.
• For each target value i, we check each number num in the array nums.
• If i - num >= 0, it means we can reach the sum i by adding num to a previous sum i - num. We update dp[i] by adding the number of ways to reach i - num.

3. Return the Result

python

return dp[target]

• Finally, we return the value of dp[target], which contains the number of ways to reach the target sum.

💡 Example Walkthrough

python

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

Output:
7

Explanation:
The possible combinations are:
1 + 1 + 1 + 1 = 4
1 + 1 + 2 = 4
1 + 2 + 1 = 4
2 + 1 + 1 = 4
2 + 2 = 4
1 + 3 = 4
3 + 1 = 4

• Initially, dp = [1, 0, 0, 0, 0] (we know that there is 1 way to form 0).
• When i = 1, dp[1] is updated by considering 1 from nums, so dp[1] = 1.
• When i = 2, dp[2] is updated by considering 1 and 2 from nums, so dp[2] = 2.
• When i = 3, dp[3] is updated by considering 1, 2, and 3 from nums, so dp[3] = 4.
• When i = 4, dp[4] is updated by considering 1, 2, and 3 from nums, so dp[4] = 7.

Thus, the result is 7, indicating that there are 7 ways to sum up to 4.

⏱️ Time & Space Complexity

MetricComplexityTime ComplexityO(target * n)Space ComplexityO(target)

• Time Complexity: We iterate over all targets from 1 to target, and for each target, we iterate over all numbers in nums. This gives a time complexity of O(target * n), where n is the length of nums.
• Space Complexity: We use a dp array of size target + 1, so the space complexity is O(target).

🧵 Final Thoughts

This problem is a great example of using dynamic programming to efficiently solve problems related to combination sums. By breaking down the problem into smaller subproblems and storing the results for those subproblems, we can optimize the process of finding the number of combinations that sum up to a target.

• Dynamic Programming: The DP approach ensures that we don’t recompute the number of combinations for the same sum multiple times.
• Bottom-Up Approach: By starting from the base case and working upwards, we build the solution incrementally, which ensures optimality.

This approach is both time-efficient and space-efficient, and is a great method to tackle problems involving combination sums and similar challenges.