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.
Flowchart Walkthrough
To analyze the problem using the Flowchart, let’s proceed with a step-by-step walkthrough to determine the suitable algorithm pattern:
Is it a graph?
- No: The problem does not deal with nodes and edges in the context of graph theory.
Need to solve for kth smallest/largest?
- No: The task is not about finding kth smallest or largest element.
Involves Linked Lists?
- No: The problem does not handle operations on linked lists.
Does the problem have small constraints?
- Yes: The size constraints allow exhaustive searching through the candidate numbers, fitting for a backtracking approach.
Brute force / Backtracking?
- Yes: Given the structure of the problem and the feasibility of exploring all combinations due to relatively small constraints, a backtracking approach is appropriate.
Conclusion: According to the flowchart, the suitable algorithm pattern for Leetcode 40. Combination Sum II is backtracking, as it necessitates exploring combinations that meet specific criteria, achievable within small constraints.
This systematic approach via the flowchart leads us to pinpoint the backtracking as the appropriate technique for this problem.
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.
Learn more about Backtracking patterns.
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:
-
Sorting the Candidates: The
candidates
array is first sorted to ensure that we can easily skip duplicates.1candidates.sort()
-
Depth-First Search (DFS) Function: The
dfs
function is defined to handle the recursion, taking two parameters:i
(the current index in thecandidates
list) ands
(the remaining sum needed to reach thetarget
).1def dfs(i: int, s: int):
-
Condition to Add to the Answer: Inside the
dfs
function, we check if the remaining sums
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[:])
-
Base Cases for Termination: We return if the index
i
moves beyond the length of thecandidates
or if the remaining sums
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
-
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)):
-
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
-
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's assume our candidates
array is [2, 5, 2, 1, 2]
, and our target
is 5
.
Following the solution approach:
- First, we sort the
candidates
to[1, 2, 2, 2, 5]
. - The
dfs
function starts withi
as0
(the first index) and thetarget
sums
as5
. - We enter a loop that will iterate through the candidates starting from index
0
. - On the first iteration,
j
is0
, and the candidate is1
.- We include
1
in our temporary combinationt
and calldfs(1, 4)
, which moves to the next index and decrements the target by the included candidate’s value (5 - 1 = 4).
- We include
- The function
dfs(1, 4)
starts and enters a loop starting at index1
; the first candidate it considers is2
.- We include
2
to make our combination[1, 2]
and calldfs(2, 2)
.
- We include
- The function
dfs(2, 2)
again finds the candidate2
at index2
.- However, this time
j
is not greater thani
, which means it's the first occurrence of this candidate in the loop, so we include2
to get[1, 2, 2]
and calldfs(3, 0)
.
- However, this time
- Since the remaning sum
s
is0
(dfs(3, 0)
), we've found a valid combination which sums to the target. So we add[1, 2, 2]
to our answer listans
. - Now, we backtrack and the temporary combination
t
becomes[1, 2]
again.- The loop in
dfs(2, 2)
continues with the nextj
as3
, but the candidate2
at index3
is a duplicate. Thus, we skip it and continue toj
as4
. Sincecandidates[4]
is5
, which is greater than our remaining sum2
, this does not lead to a valid combination. So, we finishdfs(2, 2)
without further action.
- The loop in
- We continue backtracking to
dfs(1, 4)
;t
is now[1]
.- The loop resumes with the next
j
, which is2
. But sincecandidates[2]
is a duplicate of the previous candidate, we skip it and do the same forj
as3
. - For
j
as4
, the candidate is5
, but adding5
to[1]
will exceed the remaining sum (4
). So no further action is taken.
- The loop resumes with the next
- Finally, we backtrack to the very first
dfs(0, 5)
,t
is now[]
, and we continue to the next candidate, which is2
atj
as1
.
- However, this
2
is not considered as it is a duplicate of the previous candidate.
- The next non-duplicate candidate is the
5
atj
as4
.
- We include this
5
and calldfs(5, 0)
. - Since the remaining sum
s
is0
, we've found another valid combination that sums to the target, so[5]
is added to our answer listans
.
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
.
Solution Implementation
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
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
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
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.
-
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.
-
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)
, wheren
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.
- 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:
-
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. -
Space for the temporary list
t
, which stores the current combination, will at most containn
values, adding anotherO(n)
. -
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 asO(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.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.