Master LeetCode Combination Sum II: Avoid Duplicates with Efficient Backtracking

Problem Description

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 may be used at most once.

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

Problem Analysis

The selection process can be visualized as a tree because each number can be chosen at most once. When duplicate numbers appear, they generate duplicate branches; pruning these branches eliminates duplicate results.

Sorting the array first groups identical numbers together. During backtracking, if the current number is the same as the previous one at the same recursion depth, we skip it to avoid duplicate combinations.

Reference Implementations

Java

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    List<List<Integer>> ans = new ArrayList<>();
    Arrays.sort(candidates); // sort first
    dfs(ans, new ArrayList<>(), candidates, target, 0);
    return ans;
}
private void dfs(List<List<Integer>> ans, List<Integer> path,
                 int[] candidates, int target, int start) {
    if (target == 0) {
        ans.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        if (target < candidates[i]) break; // further numbers are too large
        if (i > start && candidates[i] == candidates[i - 1]) continue; // skip duplicates
        path.add(candidates[i]);
        dfs(ans, path, candidates, target - candidates[i], i + 1);
        path.remove(path.size() - 1);
    }
}

C++

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    vector<vector<int>> ans;
    vector<int> path;
    sort(candidates.begin(), candidates.end()); // sort first
    dfs(ans, path, candidates, target, 0);
    return ans;
}
void dfs(vector<vector<int>>& ans, vector<int>& path,
         vector<int>& candidates, int target, int start) {
    if (target == 0) {
        ans.emplace_back(path);
        return;
    }
    for (int i = start; i < candidates.size(); i++) {
        if (target < candidates[i]) break;
        if (i > start && candidates[i] == candidates[i - 1]) continue; // skip duplicates
        path.emplace_back(candidates[i]);
        dfs(ans, path, candidates, target - candidates[i], i + 1);
        path.pop_back();
    }
}

C

int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}
void dfs(int **ans, int *path, int *candidates, int candidatesSize,
         int target, int start, int *returnSize,
         int **returnColumnSizes, int pathCount) {
    if (target == 0) {
        ans[*returnSize] = (int *)malloc(pathCount * sizeof(int));
        memcpy(ans[*returnSize], path, pathCount * sizeof(int));
        (*returnColumnSizes)[*returnSize] = pathCount;
        (*returnSize)++;
        return;
    }
    for (int i = start; i < candidatesSize; i++) {
        if (target < candidates[i]) break;
        if (i > start && candidates[i] == candidates[i - 1]) continue; // skip duplicates
        path[pathCount++] = candidates[i];
        dfs(ans, path, candidates, candidatesSize, target - candidates[i],
            i + 1, returnSize, returnColumnSizes, pathCount);
        pathCount--;
    }
}
int** combinationSum2(int *candidates, int candidatesSize, int target,
                     int *returnSize, int **returnColumnSizes) {
    qsort(candidates, candidatesSize, sizeof(int), cmp); // sort first
    int n = 3000;
    *returnSize = 0;
    int **ans = (int **)malloc(n * sizeof(int *));
    *returnColumnSizes = (int *)malloc(n * sizeof(int));
    int *path = (int *)malloc(n * sizeof(int));
    dfs(ans, path, candidates, candidatesSize, target, 0,
        returnSize, returnColumnSizes, 0);
    return ans;
}

Python

def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
    def backtrack(num: int, start: int):
        if num == 0:
            ans.append(path[:])
            return
        for i in range(start, len(candidates)):
            if num < candidates[i]:
                break
            if i > start and candidates[i] == candidates[i - 1]:
                continue  # skip duplicates
            path.append(candidates[i])
            backtrack(num - candidates[i], i + 1)
            path.pop()
    candidates.sort()  # sort first
    ans = []
    path = []
    backtrack(target, 0)
    return ans