377. Combination Sum IV

Loading...LeetCode

time: O(t x n), t is target, n is the length of nums

space: O(t)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function (nums, target) {
    const counts = new Array(target + 1).fill(0);
    counts[0] = 1;

    for (let i = 1; i <= target; i++) {
        let sum = 0;
        for (let j = 0; j < nums.length; j++) {
            const num = nums[j];

            const diff = i - num;
            if (diff < 0) continue;
            const count = counts[diff];
            sum += count;
        }
        counts[i] = sum;
    }

    return counts[target];
};