377. Combination Sum IV

Problem

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 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

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• All the elements of nums are unique.
• 1 <= target <= 1000

Solution (Java)

class Solution {
    private int[] storage;

    public int combinationSum4(int[] nums, int target) {
        storage = new int[target + 1];
        Arrays.fill(storage, -1);
        return result(nums, target);
    }

    private int result(int[] nums, int target) {
        if (target < 0) {
            return 0;
        }
        if (target == 0) {
            return 1;
        }
        if (storage[target] != -1) {
            return storage[target];
        }
        int count = 0;
        for (int i : nums) {
            count += result(nums, target - i);
        }
        storage[target] = count;
        return count;
    }
}

Solution (Javascript)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
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]
};

Explain:

Nope

Complexity:

• Time complexity : O(n^2).
• Space complexity : O(n).