LeetCode 40. Combination Sum II

Question

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

Source: https://leetcode.com/problems/combination-sum-ii/

Solution

This time we do not have distinct and reuse these two conveninent features. So we use pre-sorting and set to avoid duplicates.

dfs2 provides another way to skip duplicate elements on the same layer.

// depth of a dfs path is the length of the combination (variable)
// pre-sorting makes candidates with the same value be grouped together
// we can find valid candidates easily
private void dfs(int[] sortedCandidates, int startPos, int target,
                 LinkedList<Integer> current, List<List<Integer>> result) {
    if (target < 0) {
        return;
    }
    if (target == 0) {
        List<Integer> copy = new ArrayList<>(current);
        result.add(copy);
        return;
    }

    Set<Integer> used = new HashSet<>();
    // combinations in non-decreasing order
    for (int i = startPos; i < sortedCandidates.length; i++) {
        int candi = sortedCandidates[i];
        // avoid adding duplicates in the same layer
        if (used.contains(candi)) {
            continue;
        } else {
            used.add(candi);
        }
        // backtrace
        current.addLast(candi);
        dfs(sortedCandidates, i + 1, target - candi, current, result);
        current.removeLast();
    }
}

// another way to avoid duplicates
private void dfs2(int[] sortedCandidates, int startPos, int target,
                  LinkedList<Integer> current, List<List<Integer>> result) {
    if (target < 0) {
        return;
    }
    if (target == 0) {
        List<Integer> copy = new ArrayList<>(current);
        result.add(copy);
        return;
    }

    // combinations in non-decreasing order
    for (int i = startPos; i < sortedCandidates.length; i++) {
        int candi = sortedCandidates[i];
        // avoid adding duplicates in the same layer
        if (i != startPos && candi == sortedCandidates[i - 1]) {
            continue;
        }
        // backtrace
        current.addLast(candi);
        dfs2(sortedCandidates, i + 1, target - candi, current, result);
        current.removeLast();
    }
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> comb = new LinkedList<>();
    Arrays.sort(candidates);
    dfs(candidates, 0, target, comb, result);
    // dfs2(candidates, 0, target, comb, result);
    return result;
}