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[4] 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 [1].
    • The loop resumes with the next j, which is 2. But since candidates[2] 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 [1] 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 [5] is added to our answer list ans.

Finally, our dfs is done exploring all possibilities, and we have ans as [[1, 2, 2], [5]], 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) {
23            combinations.add(new ArrayList<>(combination));
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.
37            combination.add(sortedCandidates[i]);
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.
8        vector<vector<int>> answer;
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) {
19                answer.emplace_back(temp);
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.
48        return answer;
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 👨‍🏫