377. Combination Sum IV – Leetcode Solutions

Example 1:

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)
Note that different sequences are counted as different combinations.

Example 2:

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

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # Initialize a DP array with (target + 1) elements, all set to 0 initially
        dp = [0] * (target + 1)
        
        # Base case: There is one way to achieve a sum of 0 (by using no numbers)
        dp[0] = 1
        
        # Fill dp array for each sum from 1 to target
        for i in range(1, target + 1):
            # For each number in nums, check if it can be used to reach the current sum i
            for num in nums:
                if i >= num:
                    # Add the number of ways to make up (i - num) to dp[i]
                    dp[i] += dp[i - num]
        
        # The result is the number of ways to achieve the sum `target`
        return dp[target]

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        // Step 1: Create a DP array of size `target + 1` to store the number of ways 
        // to reach each sum from 0 up to `target`. Initialize all elements to 0.
        vector<unsigned int> dp(target + 1, 0);
        
        // Step 2: Base case - there is one way to reach the sum of 0, which is by not 
        // choosing any elements.
        dp[0] = 1;
        
        // Step 3: Fill the DP array. For each intermediate sum from 1 to `target`, 
        // calculate the number of ways it can be formed using the elements in `nums`.
        for (int i = 1; i <= target; i++) {
            // Step 4: For each number in `nums`, check if it can be used to form the 
            // current sum `i`. This is possible if `i - num >= 0`.
            for (int num : nums) {
                if (i - num >= 0) {
                    // Step 5: Add the number of ways to reach `i - num` to the number of ways to reach `i`.
                    dp[i] += dp[i - num];
                }
            }
        }
        
        // Step 6: The answer is the number of ways to reach the target sum.
        return dp[target];
    }
};

var combinationSum4 = function(nums, target) {
    // Initialize a dp array where dp[i] represents the number of combinations to reach sum i.
    // Set dp[0] = 1 because there is one way to reach sum 0: by choosing no elements.
    const dp = new Array(target + 1).fill(0);
    dp[0] = 1;
    
    // Loop through all possible sums from 1 to the target.
    for (let i = 1; i <= target; i++) {
        // For each sum i, iterate over all numbers in nums.
        for (let num of nums) {
            // Check if the current number can contribute to the sum i.
            if (i >= num) {
                // Add the number of ways to form (i - num) to dp[i].
                dp[i] += dp[i - num];
            }
        }
    }
    
    // dp[target] now contains the number of combinations to form the target sum.
    return dp[target];
};

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // DP array where dp[i] represents the number of ways to reach sum i
        int[] dp = new int[target + 1];
        
        // Base case: there's one way to get to 0 (by choosing no elements)
        dp[0] = 1;
        
        // Loop through each sum from 1 up to the target
        for (int currentTarget = 1; currentTarget <= target; currentTarget++) {
            // Check each number in the nums array to see if it can contribute
            for (int num : nums) {
                // Only proceed if the current number is not greater than the currentTarget
                if (num <= currentTarget) {
                    // Add the ways to get to the remaining target after using 'num'
                    dp[currentTarget] += dp[currentTarget - num];
                }
            }
        }
        
        // dp[target] now contains the number of combinations to reach 'target'
        return dp[target];
    }
}