LeetCode 377. Combination Sum IV (javascript solution)

#algorithms #javascript

Description:

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

The answer is guaranteed to fit in a 32-bit integer.

Solution:

Time Complexity : O(n^2)
Space Complexity: O(n)

var combinationSum4 = function(nums, target) {
    // Create dp array
    const dp = Array(target+1).fill(0)
    // Set default
    dp[0] = 1
    // Loop until we hit target
    for(let i = 0; i <= target;i++) {
        // Loop through all possible nums
        for(let j = 0; j < nums.length; j++) {
            // If the sum of the current position in dp and the current num is less than target, increment the index at the sum in dp array by all the ways to make dp[i]
            if(nums[j]+i <= target) dp[nums[j]+i] += dp[i]
        }
    }
    return dp[target]
};