# Concise Javascript solution for Combination Sum using DP

• 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++) {
if (i > 0) {
res[t][i - 1].forEach(way => {
res[t][i].push(way);
});
}
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];

};``````

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