LeetCode 40. Combination Sum II (javascript)

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

Constraints:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

Idea:

DFS

• Important Step: sort the array
• Create a DFS recursive and keep tracking target value and start index
  • Exit DFS recursive:
    • if (target < 0) return;
    • if (target === 0) record answer and return;
  • For loop (Possible solution) pay attention to:
    • No duplication
    • Candidates can only be used once

Solution:

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */

var combinationSum2 = function(candidates, target) {
    let res = [];
    let cur = [];
    // Important Step: sort the array
    candidates.sort();
    dfs(res, cur, 0, candidates, target);
    return res;
}

function dfs(res, cur, start, can, target) {
    // exit recursive condition
    if (target < 0) return;
    if (target === 0) {
        res.push(cur.concat());
        return;
    }
    
    for (let i = start; i < can.length; i++) {
        // skip duplicate
        if (i > start && can[i] === can[i - 1]) continue;
        cur.push(can[i]);
        // Each number in candidates may only be used once 
        // in the combination. start from i + 1
        dfs(res, cur, i + 1, can, target - can[i]);
        cur.pop();
    }
    
}