Combination Sum II

Problem

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

Solution

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    const res = [];
    backtrack(res, [], candidates.sort(), target, 0);
    return res;
};

var backtrack = function(res, path, nums, remain, start) {
    if (remain < 0) {
        return;
    } else if (remain === 0) {
        res.push([...path]);
    } else {
        for (let i = start; i < nums.length; i++) {
            if (i > start && nums[i] === nums[i - 1]) {
                continue;
            }
            path.push(nums[i]);
            backtrack(res, path, nums, remain - nums[i], i + 1);
            path.pop();
        }
    }
};

We will implement a backtracking (DFS) solution. The logic is the same as Combination Sum, except we must add an extra condition to take care of duplicate values (and can't reuse values). More specifically, we sort nums and only include duplicate elements in path if it is the first time encountering said value at said index taking into account all calls made to backtrack so far (ie. i == start).