# Combination Sum II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/combination-sum-ii)
Canonical: https://scaleengineer.com/dsa/problems/combination-sum-ii
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Array
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [Infosys](https://scaleengineer.com/companies/infosys), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Tesla](https://scaleengineer.com/companies/tesla), [Snap](https://scaleengineer.com/companies/snap)
---
## 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`

# Approaches
## Backtracking with Set for Deduplication
This approach uses a standard backtracking algorithm to find all possible combinations that sum up to the target. To handle duplicate combinations that may arise from duplicate numbers in the input array, it stores the valid combinations in a `HashSet`. This automatically filters out duplicates. The input array is sorted first to ensure that combinations like `[1, 7]` and `[7, 1]` are not generated as distinct; only the sorted version `[1, 7]` is considered.
**Time:** O(N log N + 2^N * N). Sorting takes O(N log N). The backtracking can explore up to 2^N subsets. For each valid combination, we create a copy of the list (taking up to O(N) time) and add it to a hash set (average O(N) time for list hashing). This leads to a rough upper bound of O(2^N * N). · **Space:** O(N + K * L), where N is the number of candidates, K is the number of unique combinations, and L is the average length of a combination. This includes O(N) for the recursion stack and temporary list, and O(K * L) for the hash set storing the results.
**Pros:** Relatively simple to implement as the logic for handling duplicates is offloaded to the `HashSet`.; Correctly solves the problem.
**Cons:** Less efficient due to generating many duplicate combinations that are later discarded.; The use of a `HashSet` for lists can have performance overhead due to hashing the entire list content.
### Explanation
Start with sorting the `candidates` array. This helps in two ways: it groups duplicate numbers together and it helps in generating combinations in a canonical order, which is a prerequisite for using a `Set` of lists effectively.
Define a recursive helper function, say `findCombinations(index, target, currentList, resultSet)`.
The base cases for the recursion are:
- If `target == 0`, a valid combination is found. Add a copy of `currentList` to the `resultSet`.
- If `target < 0` or `index` is out of bounds, stop this path.
In the recursive step, iterate from the current `index` to the end of the `candidates` array.
For each element `candidates[i]`, make a recursive call:
- Add `candidates[i]` to `currentList`.
- Call `findCombinations(i + 1, target - candidates[i], currentList, resultSet)`. We use `i + 1` to ensure each element is used at most once.
- Backtrack by removing `candidates[i]` from `currentList`.
The main function initializes an empty `HashSet<List<Integer>>`, calls the recursive helper, and finally converts the set to a list to return the result.
The use of a `Set` simplifies the logic for handling duplicates, as we don't need to add special checks within the recursion to avoid them. However, this comes at the cost of performance overhead from hash computations and storing potentially many redundant paths before filtering.
```java
import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Set<List<Integer>> resultSet = new HashSet<>();
        Arrays.sort(candidates); // Sorting is important for the Set to work correctly on lists
        findCombinations(candidates, 0, target, new ArrayList<>(), resultSet);
        return new ArrayList<>(resultSet);
    }

    private void findCombinations(int[] candidates, int index, int target, List<Integer> current, Set<List<Integer>> resultSet) {
        if (target == 0) {
            resultSet.add(new ArrayList<>(current));
            return;
        }
        if (target < 0) {
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            current.add(candidates[i]);
            // Move to the next index 'i + 1' since each number can be used only once
            findCombinations(candidates, i + 1, target - candidates[i], current, resultSet);
            current.remove(current.size() - 1); // Backtrack
        }
    }
}
```
### Algorithm
- Sort the `candidates` array.
- Initialize a `HashSet<List<Integer>>` to store unique combinations.
- Define a recursive function `findCombinations(index, target, currentList, resultSet)`.
- In the recursive function:
    - If `target` is 0, add a copy of `currentList` to `resultSet` and return.
    - If `target` is negative or `index` is out of bounds, return.
    - Loop from `index` to the end of `candidates`:
        - Add `candidates[i]` to `currentList`.
        - Recursively call `findCombinations(i + 1, target - candidates[i], ...)`.
        - Remove the last element from `currentList` (backtrack).
- Call the initial recursive function with `index=0`, `target`, an empty list, and the `resultSet`.
- Convert the `resultSet` to a `List` and return it.

## Optimized Backtracking with Sorting
This is the standard and most efficient approach. It enhances the basic backtracking algorithm by adding a simple but powerful check to avoid generating duplicate combinations. By first sorting the input array, we can skip over duplicate numbers at the same level of recursion, thus pruning the search tree and preventing redundant computations. This eliminates the need for a `HashSet` to filter duplicates, leading to better performance.
**Time:** O(N log N + 2^N). Sorting takes O(N log N). The backtracking part has a worst-case complexity of O(2^N), as in the worst case we might still need to explore a large portion of the subsets. However, this approach is significantly faster in practice than the Set-based approach because it prunes the search tree effectively. · **Space:** O(N). The space is dominated by the recursion stack depth, which can go up to N in the worst case. The temporary list also takes O(N) space. This does not include the space required for the output list.
**Pros:** Most efficient solution by avoiding the generation of duplicate combinations.; Avoids the overhead associated with using a `HashSet` and hashing lists.
**Cons:** The logic for skipping duplicates (`i > start && candidates[i] == candidates[i-1]`) can be slightly tricky to understand initially.
### Explanation
The core idea is to prevent the recursive function from exploring redundant paths. This is achieved by sorting the `candidates` array first.
We use a recursive helper function, `backtrack(result, tempList, candidates, remaining, start)`.
The base cases are standard: if the `remaining` target is 0, we've found a solution; if it's negative, we prune the path.
The main logic is in the loop within the recursive function. We iterate from a `start` index to avoid reusing elements and to generate combinations in a fixed order.
**The key optimization:** Inside the loop, before making a recursive call for `candidates[i]`, we check if `i > start && candidates[i] == candidates[i-1]`. If this condition is true, it means we are at a duplicate number, and we have already considered all combinations starting with the previous identical number in the current recursive call. Therefore, we can safely `continue` to the next iteration, skipping the current duplicate element. This single line of code effectively prunes the search space to avoid duplicate combinations.
This way, we build only unique combinations directly into the result list, avoiding the overhead of a `Set`.
```java
import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates); // Sort candidates to handle duplicates
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
        if (remain < 0) {
            return;
        } else if (remain == 0) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int i = start; i < candidates.length; i++) {
                // Skip duplicates to avoid duplicate combinations
                if (i > start && candidates[i] == candidates[i-1]) {
                    continue;
                }
                tempList.add(candidates[i]);
                // Recurse with the next starting index and reduced target
                backtrack(result, tempList, candidates, remain - candidates[i], i + 1);
                tempList.remove(tempList.size() - 1); // Backtrack
            }
        }
    }
}
```
### Algorithm
- Sort the `candidates` array.
- Initialize an empty `List<List<Integer>>` to store the results.
- Define a recursive function `backtrack(result, tempList, candidates, remaining, start)`.
- In the recursive function:
    - If `remaining` is 0, add a copy of `tempList` to `result` and return.
    - If `remaining` is negative, return.
    - Loop from `start` to the end of `candidates`:
        - If `i > start` and `candidates[i] == candidates[i-1]`, `continue` to the next iteration to skip duplicates.
        - Add `candidates[i]` to `tempList`.
        - Recursively call `backtrack(..., remaining - candidates[i], i + 1)`.
        - Remove the last element from `tempList` (backtrack).
- Call the initial `backtrack` function with `start=0`.
- Return the `result` list.

# Solutions
### CSharp

```csharp
public class Solution {
    private List < IList < int >> ans = new List < IList < int >> ();
    private List < int > t = new List < int > ();
    private int[] candidates;
    public IList < IList < int >> CombinationSum2(int[] candidates, int target) {
        Array.Sort(candidates);
        this.candidates = candidates;
        dfs(0, target);
        return ans;
    }
    private void dfs(int i, int s) {
        if (s == 0) {
            ans.Add(new List < int > (t));
            return;
        }
        if (i >= candidates.Length || s < candidates[i]) {
            return;
        }
        for (int j = i; j < candidates.Length; ++j) {
            if (j > i && candidates[j] == candidates[j - 1]) {
                continue;
            }
            t.Add(candidates[j]);
            dfs(j + 1, s - candidates[j]);
            t.RemoveAt(t.Count - 1);
        }
    }
}
```

### Java

```java
class Solution {
private
  List<List<Integer>> ans = new ArrayList<>();
private
  List<Integer> t = new ArrayList<>();
private
  int[] candidates;
public
  List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    this.candidates = candidates;
    dfs(0, target);
    return ans;
  }
private
  void dfs(int i, int s) {
    if (s == 0) {
      ans.add(new ArrayList<>(t));
      return;
    }
    if (i >= candidates.length || s < candidates[i]) {
      return;
    }
    for (int j = i; j < candidates.length; ++j) {
      if (j > i && candidates[j] == candidates[j - 1]) {
        continue;
      }
      t.add(candidates[j]);
      dfs(j + 1, s - candidates[j]);
      t.remove(t.size() - 1);
    }
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */ var combinationSum2 =
  function (candidates, target) {
    candidates.sort((a, b) => a - b);
    const ans = [];
    const t = [];
    const dfs = (i, s) => {
      if (s === 0) {
        ans.push(t.slice());
        return;
      }
      if (i >= candidates.length || s < candidates[i]) {
        return;
      }
      for (let j = i; j < candidates.length; ++j) {
        if (j > i && candidates[j] === candidates[j - 1]) {
          continue;
        }
        t.push(candidates[j]);
        dfs(j + 1, s - candidates[j]);
        t.pop();
      }
    };
    dfs(0, target);
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> ans;
    vector<int> t;
    function<void(int, int)> dfs = [&](int i, int s) {
      if (s == 0) {
        ans.emplace_back(t);
        return;
      }
      if (i >= candidates.size() || s < candidates[i]) {
        return;
      }
      for (int j = i; j < candidates.size(); ++j) {
        if (j > i && candidates[j] == candidates[j - 1]) {
          continue;
        }
        t.emplace_back(candidates[j]);
        dfs(j + 1, s - candidates[j]);
        t.pop_back();
      }
    };
    dfs(0, target);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: def dfs(i, s): if s > target: return if s == target: ans . append(t . copy()) return for j in range(i, len(candidates)):  # or: if i == j or candidates[j] != candidates[j - 1] if j > i and candidates [ j ] == candidates [ j - 1 ]: continue t . append ( candidates [ j ]) dfs ( j + 1 , s + candidates [ j ]) t . pop () ans = [] candidates . sort () t = [] dfs ( 0 , 0 ) return ans ############ class Solution ( object ): def combinationSum2 ( self , candidates , target ): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ def dfs ( nums , target , start , visited , path , res ): if target == 0 : res . append ( path + []) return for i in range ( start , len ( nums )): if i > start and nums [ i ] == nums [ i - 1 ]: continue if target - nums [ i ] < 0 : return 0 if i not in visited : visited . add ( i ) path . append ( nums [ i ]) dfs ( nums , target - nums [ i ], i + 1 , visited , path , res ) path . pop () visited . discard ( i ) candidates . sort () res = [] visited = set ([]) dfs ( candidates , target , 0 , visited , [], res ) return res

```