Given an array of integers candidates and a target value target, find all unique combinations in candidates where the numbers sum to target.

Key constraints:

• Each number can only be used once in each combination.
• All numbers (including the target) are positive integers.
• The result set must not contain duplicate combinations.

Examples

Example 1:

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

Example 2:

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

Analysis

This problem differs from the standard Combination Sum in two critical ways:

1. Each element can only be selected once per combination (unlike the previous problem where elements could be reused).
2. The input array may contain duplicate values, but the output must not contain duplicate combinations.

The Core Challenge: Removing Duplicates

The primary difficulty lies in handling duplicate elements while avoiding duplicate combinations. Naively generating all combinations and using a set for deduplication is inefficient and can easily timeout.

The key insight is that duplicates must be filtered during the search processs itself. In the tree structure representation of combination problems, "used" elements exist in two dimensions:

• Same branch: Elements used within a single combination path
• Same level: Elements at the same tree depth across different branches

Within a combination, elements can repeat freely—the same value can appear multiple times (like [1, 1, 6] in Example 1). What we must avoid is having identical combinations as separate results.

Therefore, we need to filter duplicates at the same tree level, not with in the same branch.

Tree Structure Visualization

Consider candidates = [1, 1, 2] and target = 3 (sorted for convenience):

The tree structure reveals that when we encounter duplicate values, we must skip processing the duplicate at the same level. This requires the array to be sorted first, so identical value are adjacent.

Backtracking Framework

1. Function Parameters

A boolean array used tracks whether each element has been visited on the current branch. This array is essential for distinguishing between same-level and same-branch usage.

vector<vector>> combinations;
vector<int> currentCombo;

void backtrack(vector<int>& nums, int target, int sum, int start, vector<bool>& used) {
    // Implementation...
}
</bool></int></int></vector>

2. Termination Condition

The recursion stops when the current sum reaches the target.

if (sum == target) {
    combinations.push_back(currentCombo);
    return;
}

3. Single-Level Search Logic

The deduplication condition is the critical part:

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    continue;
}

When nums[i] == nums[i - 1] and used[i - 1] == false, it indicates that nums[i - 1] was processed at the same level in a previous iteration. Skipping nums[i] prevents generating duplicate combinations.

The interpretation of used[i - 1]:

• used[i - 1] == true: The previous value was used on the current branch (descended into recursion)
• used[i - 1] == false: The previous value was processed at the same level

Only when used[i - 1] == false should we skip the current element to avoid same-level duplicates.

Complete Implementation

class Solution {
private:
    vector<vector>> combinations;
    vector<int> currentCombo;
    
    void backtrack(vector<int>& nums, int target, int sum, int start, vector<bool>& used) {
        if (sum == target) {
            combinations.push_back(currentCombo);
            return;
        }
        
        for (int i = start; i < nums.size() && sum + nums[i] <= target; i++) {
            // Skip duplicates at the same tree level
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            
            sum += nums[i];
            currentCombo.push_back(nums[i]);
            used[i] = true;
            
            backtrack(nums, target, sum, i + 1, used);
            
            used[i] = false;
            sum -= nums[i];
            currentCombo.pop_back();
        }
    }

public:
    vector<vector>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(), false);
        combinations.clear();
        currentCombo.clear();
        
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, 0, 0, used);
        return combinations;
    }
};
</bool></int></vector></bool></int></int></vector>

The pruning condition sum + candidates[i] <= target eliminates branches that cannot possibly reach the target.

Complexity Analysis

• Time Complexity: O(n * 2^n)
• Space Complexity: O(n)

Alternative Approach Without Used Array

The same result can be achieved using startIndex directly for deduplication:

class Solution {
private:
    vector<vector>> combinations;
    vector<int> currentCombo;
    
    void backtrack(vector<int>& nums, int target, int sum, int start) {
        if (sum == target) {
            combinations.push_back(currentCombo);
            return;
        }
        
        for (int i = start; i < nums.size() && sum + nums[i] <= target; i++) {
            // Skip duplicates: only check when i > startIndex
            // This ensures we're comparing with the immediate predecessor at the same level
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            
            sum += nums[i];
            currentCombo.push_back(nums[i]);
            backtrack(nums, target, sum, i + 1);
            sum -= nums[i];
            currentCombo.pop_back();
        }
    }

public:
    vector<vector>> combinationSum2(vector<int>& candidates, int target) {
        combinations.clear();
        currentCombo.clear();
        
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, 0, 0);
        return combinations;
    }
};
</int></vector></int></int></vector>

In this version, the condition i > start naturally excludes cases where we've descended into recursion (the branch change), making the used array unnecessary.