Concise Javascript solution for Combination Sum using DP


  • 0
    D

    Using dynamic programming:
    res[t][i] - result of subproblem with target t and pick from candidates[0] to candidates[i].

    For every combination add up to t, each number of combination has a corresponding index in the array. Let max_id is the maximum of those indices. This combination will be found exactly once in the loop (t, max_id). So there is no duplicate.

     * @param {number[]} candidates
     * @param {number} target
     * @return {number[][]}
     */
    var combinationSum = function(candidates, target) {
        let res = new Array(target + 1);
        for (let t = 0; t <= target; t++) {
            res[t] = new Array(candidates.length);
            for (let i = 0; i < candidates.length; i++) {
                res[t][i] = [];
            }
        }
        // res[t][i] = solutions of subproblem of target t and pick from candidates[0..i];
        
        // initialize
        for (let i = 0; i < candidates.length; i++) {
            res[0][i] = [[]];
        }
        
        for (let t = 1; t <= target; t++) {
            for (let i = 0; i < candidates.length; i++) {
                // solutions not start with candidates[i]
                if (i > 0) {
                    res[t][i - 1].forEach(way => {
                        res[t][i].push(way);
                    });
                }
                // solutions start with candidates[i]
                if (candidates[i] <= t)  {
                    // console.log(t + ", " + i);
                    res[t - candidates[i]][i].forEach(way => {
                        res[t][i].push(way.concat(candidates[i]));
                    });
                }
            }
        }
        
        return res[target][candidates.length - 1];
        
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.