# 40. Combination Sum II

## Problem Description

In this problem, we are given a set of candidate numbers (an array `candidates`) and a target number (`target`). Our goal is to find all unique combinations where the sum of the numbers in each combination equals the `target`. Importantly, we can only use each number in `candidates` once in any given combination.

Another important requirement is that the solution set must not include any duplicate combinations. Even though the same number can occur multiple times in the `candidates`, it can only appear once in each combination.

Essentially, we need to explore all possible combinations of the numbers that add up to the `target` and return a list of all combinations that meet the criteria without any repetitions.

## Intuition

The intuition behind the solution involves a backtracking technique, which is similar to depth-first search (DFS).

Since we need to find all combinations that add up to the target and any number in the candidates can be used only once, we sort the candidates first. Sorting the array helps us to easily skip over duplicate elements and avoid generating duplicate combinations.

Then, we perform DFS with backtracking, starting from the beginning of the `candidates` array and exploring each possibility by either including or excluding a candidate. After including a candidate in the combination, we call the function recursively, reducing the `target` by the value of that candidate and moving to the next index.

While exploring, we keep track of the current sum of the combination, and when the sum equals the target, we add the current combination to the answer. If at any point, the sum exceeds `target` or we reach the end of the candidates array, we backtrack.

To prevent duplicates, we skip subsequent candidates that are the same as the previous one at each stage in the loop. This way, we ensure that if a number has been used in a combination, the same number is not used immediately again to form another similar combination.

The result of the function will be a list of lists, where each inner list is a unique combination of numbers that sum to the target value.

## Solution Approach

The solution uses depth-first search (DFS), backtracking, and sorting to effectively find all unique combinations. Let's break down how each part of the code contributes to the solution:

1. Sorting the Candidates: The `candidates` array is first sorted to ensure that we can easily skip duplicates.

``1candidates.sort()``
2. Depth-First Search (DFS) Function: The `dfs` function is defined to handle the recursion, taking two parameters: `i` (the current index in the `candidates` list) and `s` (the remaining sum needed to reach the `target`).

``1def dfs(i: int, s: int):``
3. Condition to Add to the Answer: Inside the `dfs` function, we check if the remaining sum `s` is zero, meaning we found a valid combination that sums to the target. In that case, we add a copy of the current combination to the answer list.

``````1if s == 0:
2    ans.append(t[:])``````
4. Base Cases for Termination: We return if the index `i` moves beyond the length of the `candidates` or if the remaining sum `s` is less than the current candidate, which means we can't reach the desired total with the current and subsequent candidates since they are all larger.

``````1if i >= len(candidates) or s < candidates[i]:
2    return``````
5. Loop Over the Candidates: Starting from the current index to the end of `candidates`, we try to include the candidate in the combination:

``1for j in range(i, len(candidates)):``
6. Skipping Duplicates: Before including a candidate in the combination, we skip over it if it's the same as its predecessor to avoid duplicates in our answer list (since we’ve already considered this value in the previous steps).

``````1if j > i and candidates[j] == candidates[j - 1]:
2    continue``````
7. Backtracking: After including a candidate, the `dfs` function is called recursively with the updated index (`j+1`) and the updated remaining sum (`s - candidates[j]`). After this recursive call, we backtrack by removing the last candidate from the combination and moving on to the next candidate.

``````1t.append(candidates[j])
2dfs(j + 1, s - candidates[j])
3t.pop()``````

The solution utilizes a list `ans` to store all the unique combinations and a temporary list `t` to store the current combination being constructed.

After defining `dfs`, the solution begins the search with:

``````1ans = []
2t = []
3dfs(0, target)``````

The DFS and backtracking continue until all possible combinations that meet the criteria have been explored, after which `ans` is returned, containing all the valid combinations.

This approach efficiently explores all possible combinations and prunes the search space to avoid duplicates and unnecessary searches, thereby finding the solution set in an optimal manner.

### Example Walkthrough

Let's assume our `candidates` array is `[2, 5, 2, 1, 2]`, and our `target` is `5`.

Following the solution approach:

1. First, we sort the `candidates` to `[1, 2, 2, 2, 5]`.
2. The `dfs` function starts with `i` as `0` (the first index) and the `target` sum `s` as `5`.
3. We enter a loop that will iterate through the candidates starting from index `0`.
4. On the first iteration, `j` is `0`, and the candidate is `1`.
• We include `1` in our temporary combination `t` and call `dfs(1, 4)`, which moves to the next index and decrements the target by the included candidate’s value (5 - 1 = 4).
5. The function `dfs(1, 4)` starts and enters a loop starting at index `1`; the first candidate it considers is `2`.
• We include `2` to make our combination `[1, 2]` and call `dfs(2, 2)`.
6. The function `dfs(2, 2)` again finds the candidate `2` at index `2`.
• However, this time `j` is not greater than `i`, which means it's the first occurrence of this candidate in the loop, so we include `2` to get `[1, 2, 2]` and call `dfs(3, 0)`.
7. Since the remaning sum `s` is `0` (`dfs(3, 0)`), we've found a valid combination which sums to the target. So we add `[1, 2, 2]` to our answer list `ans`.
8. Now, we backtrack and the temporary combination `t` becomes `[1, 2]` again.
• The loop in `dfs(2, 2)` continues with the next `j` as `3`, but the candidate `2` at index `3` is a duplicate. Thus, we skip it and continue to `j` as `4`. Since `candidates` is `5`, which is greater than our remaining sum `2`, this does not lead to a valid combination. So, we finish `dfs(2, 2)` without further action.
9. We continue backtracking to `dfs(1, 4)`; `t` is now ``.
• The loop resumes with the next `j`, which is `2`. But since `candidates` is a duplicate of the previous candidate, we skip it and do the same for `j` as `3`.
• For `j` as `4`, the candidate is `5`, but adding `5` to `` will exceed the remaining sum (`4`). So no further action is taken.
10. Finally, we backtrack to the very first `dfs(0, 5)`, `t` is now `[]`, and we continue to the next candidate, which is `2` at `j` as `1`.
• However, this `2` is not considered as it is a duplicate of the previous candidate.
1. The next non-duplicate candidate is the `5` at `j` as `4`.
• We include this `5` and call `dfs(5, 0)`.
• Since the remaining sum `s` is `0`, we've found another valid combination that sums to the target, so `` is added to our answer list `ans`.

Finally, our `dfs` is done exploring all possibilities, and we have `ans` as `[[1, 2, 2], ]`, which are the unique combinations that sum to the target `5`.

## Python Solution

``````1from typing import List
2
3class Solution:
4    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
5        # Helper function to perform depth-first search
6        def dfs(start_index: int, current_sum: int):
7            # If the current sum is 0, we found a valid combination
8            if current_sum == 0:
9                combinations.append(combination[:])
10                return
11            # If the index is out of bounds or the current element is larger than the current_sum, stop recursion
12            if start_index >= len(candidates) or current_sum < candidates[start_index]:
13                return
14
15            # Iterate over the candidates starting from the current index
16            for i in range(start_index, len(candidates)):
17                # Skip duplicates to avoid repeating the same combination
18                if i > start_index and candidates[i] == candidates[i - 1]:
19                    continue
20                # Add the current candidate to the current combination
21                combination.append(candidates[i])
22                # Recursively call dfs with the next index and the remaining sum
23                dfs(i + 1, current_sum - candidates[i])
24                # Backtrack by removing the last added candidate
25                combination.pop()
26
27        # Sort the candidates to handle duplicates easily
28        candidates.sort()
29        # This list will hold all unique combinations
30        combinations = []
31        # This temp list will store the current combination
32        combination = []
33        # Start the depth-first search
34        dfs(0, target)
35        # Return all unique combinations that add up to the target
36        return combinations
37
38# Example usage:
39# sol = Solution()
40# result = sol.combinationSum2([10,1,2,7,6,1,5], 8)
41# print(result)  # Output would be a list of lists with all the unique combinations
42``````

## Java Solution

``````1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5public class Solution {
6
7    private List<List<Integer>> combinations = new ArrayList<>(); // List to hold the final combinations.
8    private List<Integer> combination = new ArrayList<>(); // Temporary list to hold a single combination.
9    private int[] sortedCandidates; // Array to hold the input candidates after sorting.
10
11    // Method to find all possible unique combinations that add up to the target.
12    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
13        Arrays.sort(candidates); // Sort the array to handle duplicates and to make it easier to prune branches.
14        sortedCandidates = candidates; // Storing the sorted array in an instance variable for easy access.
15        backtrack(0, target); // Begin the backtrack algorithm.
16        return combinations; // Return the final list of combinations.
17    }
18
19    // Backtrack method to find all valid combinations.
20    private void backtrack(int startIndex, int remainingSum) {
21        // If the remaining sum is 0, the current combination is a valid combination.
22        if (remainingSum == 0) {
24            return;
25        }
26        // If the startIndex is out of bounds or the smallest candidate is greater than the remainingSum, there are no valid combinations.
27        if (startIndex >= sortedCandidates.length || remainingSum < sortedCandidates[startIndex]) {
28            return;
29        }
30        // Iterate through the candidates starting from startIndex.
31        for (int i = startIndex; i < sortedCandidates.length; ++i) {
32            // Skip duplicates to avoid redundant combinations.
33            if (i > startIndex && sortedCandidates[i] == sortedCandidates[i - 1]) {
34                continue;
35            }
36            // Add the candidate to the current combination.
38            // Recursively call the method with the next index and the updated remaining sum.
39            backtrack(i + 1, remainingSum - sortedCandidates[i]);
40            // Backtrack: remove the last added candidate to try other candidates.
41            combination.remove(combination.size() - 1);
42        }
43    }
44}
45``````

## C++ Solution

``````1class Solution {
2public:
3    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
4        // Sort the candidate numbers to handle duplicates and ease the combination process.
5        sort(candidates.begin(), candidates.end());
6
7        // Initialize the answer vector that will hold all unique combinations.
9
10        // Temporary vector to store individual combinations.
11        vector<int> temp;
12
13        // Define a recursive lambda function to perform deep-first search (DFS) for combinations.
14        // 'currentIndex' is the start index for exploring candidates,
15        // and 'currentSum' is the remaining sum we need to hit the target.
16        function<void(int, int)> dfs = [&](int currentIndex, int currentSum) {
17            // Base case: if remaining sum is zero, we found a valid combination.
18            if (currentSum == 0) {
20                return;
21            }
22            // If out of bounds or the current number exceeds the remaining sum, backtrack.
23            if (currentIndex >= candidates.size() || currentSum < candidates[currentIndex]) {
24                return;
25            }
26
27            // Iterate through the candidates starting from 'currentIndex'.
28            for (int j = currentIndex; j < candidates.size(); ++j) {
29                // Skip duplicates to guarantee uniqueness of combinations.
30                if (j > currentIndex && candidates[j] == candidates[j - 1]) {
31                    continue;
32                }
33                // Choose candidate 'j' and go deeper into the recursion tree.
34                temp.emplace_back(candidates[j]);
35
36                // Recurse with the next index and the new remaining sum.
37                dfs(j + 1, currentSum - candidates[j]);
38
39                // Backtrack and remove the previously chosen candidate.
40                temp.pop_back();
41            }
42        };
43
44        // Start the DFS process with index 0 and the target sum.
45        dfs(0, target);
46
47        // Return all unique combinations that add up to the target.
49    }
50};
51``````

## Typescript Solution

``````1// This function finds all unique combinations of candidates where the candidate numbers sum to target.
2// Each number in candidates may only be used once in the combination.
3// It returns a list of all unique combinations.
4function combinationSum2(candidates: number[], target: number): number[][] {
5    // First, sort the input candidates to simplify the process of skipping duplicates
6    candidates.sort((a, b) => a - b);
7    // This will hold all the unique combinations that meet the target sum
8    const combinations: number[][] = [];
9    // Temporary array to store one potential combination
10    const tempCombination: number[] = [];
11    // Depth-first search function to explore all possibilities
12    const dfs = (startIndex: number, remainingSum: number) => {
13        // If remaining sum is zero, we found a valid combination
14        if (remainingSum === 0) {
15            // Add a copy of the current combination to the final results
16            combinations.push(tempCombination.slice());
17            return;
18        }
19        // If the startIndex is out of bounds or the smallest candidate exceeds the remainingSum
20        // there's no need to continue exploring this path
21        if (startIndex >= candidates.length || remainingSum < candidates[startIndex]) {
22            return;
23        }
24
25        // Iterate over the candidates starting from the startIndex
26        for (let i = startIndex; i < candidates.length; i++) {
27            // Skip duplicate elements to prevent duplicate combinations
28            if (i > startIndex && candidates[i] === candidates[i - 1]) {
29                continue;
30            }
31            // Include the current candidate in the temporary combination
32            tempCombination.push(candidates[i]);
33            // Continue exploring further with the next candidates and a reduced remaining sum
34            dfs(i + 1, remainingSum - candidates[i]);
35            // Backtrack and remove the last candidate from the combination
36            tempCombination.pop();
37        }
38    };
39
40    // Initialize the depth-first search with starting index 0 and the initial target sum
41    dfs(0, target);
42    // Return all unique combinations found that sum up to the target
43    return combinations;
44}
45``````

## Time and Space Complexity

The provided Python code solves the combination sum problem where each number in the array `candidates` can only be used once to find all unique combinations that sum up to a given target.

### Time Complexity

The time complexity of this code primarily depends on the depth of the recursion and the number of recursive calls made at each level.

1. The recursion depth is at most the target value if we choose candidates with a value of 1 every time. However, since the same candidate cannot be used repeatedly, the recursion depth is constrained by the number of candidates in the worst case.

2. At every level of recursion, we iterate over the remaining candidates, so, in the worst case, the number of recursive calls can be exponential in nature, implied by `O(2^n)`, where `n` is the number of candidates. However, since we skip duplicates after sorting, the number of branches in the recursion tree can be less than that.

A more accurate bound is not straightforward because it depends on the candidates and the target value. The worst-case time complexity, without considering duplicates, is `O(2^n)`, where `n` is the number of candidates.

1. The sorting operation at the start of the code takes `O(n*log(n))` time.

Combining the sorting with the recursion leads to a worst-case time complexity of `O(n*log(n) + 2^n)`. Considering that the exponential part is more dominant, we can approximate it as `O(2^n)`.

### Space Complexity

The space complexity of the code consists of:

1. Space used by the recursion stack, which in the worst case is equivalent to the depth of recursion, at most `O(n)` if all candidates are used.

2. Space for the temporary list `t`, which stores the current combination, will at most contain `n` values, adding another `O(n)`.

3. Finally, the output list `ans` that could potentially hold all unique combinations of candidates. In the worst case, this could be all possible combinations which can be exponential, represented as `O(2^n)`.

Hence, the overall space complexity, considering the output space and the recursion stack depth, is `O(n + 2^n)`. Typically, the output space can be a separate consideration, and if we exclude it, the space complexity for computation is `O(n)`. However, if we include the space needed for the output, it would be `O(2^n)` due to the possibility of storing all combinations.

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

TA 👨‍🏫