Problem Description

Given a collection of candidate numbers candidates (which may contain duplicates) 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.
• The solution set must not contain duplicate combinations.
• Return the list of all unique combinations as a list of lists.

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

Constraints:

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

Thought Process

The problem asks us to find all unique combinations of numbers from a list that add up to a given target, with the restriction that each number may be used at most once per combination. Since the input may contain duplicate numbers, we must avoid returning duplicate combinations.

A brute-force approach would be to generate all possible subsets and filter those that sum up to the target, but this is inefficient and may produce duplicate results if the input has repeated numbers.

To optimize, we can:

• Sort the input array to easily skip duplicates.
• Use backtracking to efficiently explore possible combinations.
• Ensure that each number is used only once per combination by controlling the recursion start index.
• Skip over duplicate numbers at the same recursion depth to avoid repeated combinations.

Solution Approach

Let's break down the solution step by step:

1. Sort the Input: Sorting candidates helps us easily identify and skip duplicates during backtracking.
2. Backtracking Function: We define a recursive function that:
   • Keeps track of the current combination and its sum.
   • Takes a start index to ensure each element is only used once per combination.
3. Base Cases:
   • If the sum of the current combination equals target, add it to the result.
   • If the sum exceeds target, stop exploring this path (prune the branch).
4. Recursive Exploration:
   • Loop through the candidates starting from start index.
   • Skip duplicate numbers by checking if the current number is the same as the previous (and not at the start of the loop).
   • Add the current number to the combination and recursively explore further with the next index.
   • Backtrack by removing the last number before moving to the next candidate.
5. Result: Collect all valid combinations in a result list.

This method ensures that:

• Each number is used at most once per combination.
• No duplicate combinations are produced, even if the input has repeated numbers.

Example Walkthrough

Let's use candidates = [10,1,2,7,6,1,5] and target = 8 as an example.

1. Sort candidates: [1,1,2,5,6,7,10]
2. Start backtracking:
   • First pick 1 (index 0), remaining target = 7
   • Pick next 1 (index 1), remaining target = 6
   • Pick 2 (index 2), remaining target = 4
   • Pick 5 (index 3), remaining target = -1 (too high, backtrack)
   • Backtrack, try 6 (index 4), remaining target = 0 (found: [1,1,6])
   • Backtrack, try 7 (index 5), remaining target = -1 (too high, backtrack)
   • Backtrack to [1], try 2 (index 2), remaining target = 5
   • Pick 5 (index 3), remaining target = 0 (found: [1,2,5])
   • Backtrack, try 6 (index 4), remaining target = -1
   • Backtrack, try 7 (index 5), remaining target = -2
   • Backtrack to [1], try 5 (index 3), remaining target = 2
   • Backtrack, try 6 (index 4), remaining target = 1
   • Backtrack, try 7 (index 5), remaining target = 0 (found: [1,7])
   • Continue with 2 (index 2) as the first pick, remaining target = 6
   • Pick 5 (index 3), remaining target = 1
   • Pick 6 (index 4), remaining target = 0 (found: [2,6])
   • Continue this way, skipping duplicates at the same recursion depth.
3. Resulting combinations: [ [1,1,6], [1,2,5], [1,7], [2,6] ]

Notice how we skip the second '1' at the same recursion depth to avoid duplicate combinations.

Time and Space Complexity

Brute-force:
Generating all possible subsets of n elements is O(2^n), and checking the sum for each subset is O(n), so total is O(n*2^n). Additionally, we would need to filter out duplicates, which adds further overhead.

Optimized Backtracking:
The number of unique combinations is less than all possible subsets, but in the worst case (with all small numbers and a large target), the algorithm still explores many paths, so time complexity is O(2^n) in the worst case. However, pruning (stopping when the sum exceeds target) and skipping duplicates significantly reduces the practical number of recursive calls.
Space complexity is O(n) for the recursion stack and combination storage, plus O(k) for the total number of valid combinations returned (where k is the number of solutions).

Summary

In this problem, we efficiently find all unique combinations that sum up to a target by using backtracking with careful duplicate skipping. Sorting the candidates enables us to avoid redundant work and ensures each combination is unique. By pruning impossible paths early and only exploring valid options, we achieve both correctness and efficiency. The elegance of the solution lies in its clarity and the way it leverages sorting and recursion to manage constraints.

Code Implementation

class Solution:
    def combinationSum2(self, candidates, target):
        candidates.sort()
        res = []
        def backtrack(start, path, total):
            if total == target:
                res.append(path[:])
                return
            if total > target:
                return
            prev = -1
            for i in range(start, len(candidates)):
                if candidates[i] == prev:
                    continue
                path.append(candidates[i])
                backtrack(i + 1, path, total + candidates[i])
                path.pop()
                prev = candidates[i]
        backtrack(0, [], 0)
        return res
      

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> res;
        vector<int> path;
        backtrack(candidates, target, 0, path, res);
        return res;
    }
    void backtrack(vector<int>& candidates, int target, int start, vector<int>& path, vector<vector<int>>& res) {
        if (target == 0) {
            res.push_back(path);
            return;
        }
        if (target < 0) return;
        int prev = -1;
        for (int i = start; i < candidates.size(); ++i) {
            if (candidates[i] == prev) continue;
            path.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, res);
            path.pop_back();
            prev = candidates[i];
        }
    }
};
      

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (target < 0) return;
        int prev = -1;
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] == prev) continue;
            path.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, res);
            path.remove(path.size() - 1);
            prev = candidates[i];
        }
    }
}
      

var combinationSum2 = function(candidates, target) {
    candidates.sort((a, b) => a - b);
    const res = [];
    function backtrack(start, path, total) {
        if (total === target) {
            res.push([...path]);
            return;
        }
        if (total > target) return;
        let prev = -1;
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] === prev) continue;
            path.push(candidates[i]);
            backtrack(i + 1, path, total + candidates[i]);
            path.pop();
            prev = candidates[i];
        }
    }
    backtrack(0, [], 0);
    return res;
};