Given an array of distinct integers, nums, and an integer, target, return a list of all unique combinations of nums where the chosen numbers sum up to the target. The combinations may be returned in any order. An integer from nums may be chosen an unlimited number of times.

combination-sum.js

function combinationSum(nums, target) {
    // prepare a dp array
    // indexes are target values up to target
    // for example dp [3] contains all unique combinations that add up to 3
    // so at the end we will be able to return dp[target]
    const dp = Array(target + 1).fill().map(() => []);
    // the only combination that sums up to 0 is an empty combination
    dp[0] = [[]]
    // start iterating target values, from 1 to target including
    for (let subTar = 1; subTar <= target; ++subTar) {
        // at each subtarget, iterate all nums
        for (let i = 0; i < nums.length; ++i) {
            const num = nums[i];
            // ignore num if it's larger than the subtarget
            if (num > subTar) {
                continue
            }
            // here num is either less than or equal to subtarget
            // so we can build combinations with it
            // iterate "leftover" combinations from dp
            // meaning dp[subTar - num], where subTar - num is some other subtarget less than subTar,
            // which we have previously processed
            const leftovers = dp[subTar - num];
            const existingCombos = dp[subTar];
            for (let j = 0; j < leftovers.length; ++j) {
                // all leftover combinations add up to subTar - num
                // which means all the same combinations, but with num added, will be adding up to subTar
                // (optimal substructure)
                // so build this new combination
                const combo = [...leftovers[j], num];
                // now the requirement is that we only hold unique combinations
                // meaning 2,1 and 1,2 is the same combination and only one of those should be included
                // so we sort our new combinations, 
                // and check if we already have such combinations at db[subTar]
                // (we could have the same combinations while iterating previous nums)
                combo.sort((a, b) => a - b);
                if (!existingCombos.find(existingCombo => existingCombo.join("") === combo.join(""))) {
                    existingCombos.push(combo)
                }
            }
        }
    }
    return dp[target]; 
}


export {
    combinationSum
}

// tc: sorting takes O(s log s), where s = t / m, where m is the min element in nums
// why? well if min is 1, and t = 9, longest combo is 9 1s. if min is 3, longest combo is just 3 3s.
// the sorting runs inside of the second inner loop, so thats s*s log s, so s^2logs
// the first inner loop runs n times, the outer t times
// so O(t * n * s^2log(s))
// sc: O(t * n)