Combination Sum II 🧠
LeetCode Link: Combination Sum II
Difficulty: Medium
Problem Explanation 📝
Problem: LeetCode 40 - Combination Sum II
Description: 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.
Intuition: To find all unique combinations that sum to the target, we can use a backtracking approach. The idea is to generate all possible combinations by trying out different candidate elements at each step. However, we need to skip duplicate combinations to avoid duplicates in the solution set.
Approach:
- Sort the input array
candidates
to handle duplicates and generate combinations in a non-decreasing order. - Initialize an empty vector
combination
to store the current combination. - Initialize an empty vector
result
to store all valid combinations. - Define a helper function
backtrack
:
- If the current sum is equal to the target, add the current combination to the
result
vector. - Otherwise:
- Iterate through the candidates from the current index to the end:
- If the current candidate is greater than the remaining target, break the loop (as the remaining candidates will be larger and won't fit).
- If the current candidate is a duplicate (not the first occurrence), skip it to avoid duplicate combinations.
- Include the current candidate in the combination.
- Recursively call
backtrack
with the updated sum and the next index. - Exclude the current candidate from the combination.
- Call the
backtrack
function with the initial sum of 0 and index 0. - Return the
result
vector containing all valid combinations.
⌛ Time Complexity:
The time complexity is O(2^n), where n is the size of the input array candidates
. This is because there are 2^n possible combinations, and we generate all of them.
💾 Space Complexity:
The space complexity is O(n), where n is the size of the input array candidates
. This is because we store the combinations in the result
vector.
Solutions 💡
Cpp 💻
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
vector<vector<int>> result;
vector<int> combination;
sort(candidates.begin(), candidates.end()); // Sort the candidates
backtrack(candidates, target, 0, combination, result);
return result;
}
private:
void backtrack(const vector<int> &candidates, int target, int index, vector<int> &combination, vector<vector<int>> &result) {
if (target == 0) {
result.push_back(combination);
return;
}
for (int i = index; i < candidates.size(); ++i) {
if (candidates[i] > target) {
break; // Skip remaining candidates since they will be larger and won't fit
}
if (i > index && candidates[i] == candidates[i - 1]) {
continue; // Skip duplicate candidates to avoid duplicate combinations
}
combination.push_back(candidates[i]); // Include the current candidate
backtrack(candidates, target - candidates[i], i + 1, combination, result); // Recursively call with updated target and next index
combination.pop_back(); // Exclude the current candidate (backtrack)
}
}
};
Python 🐍
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(start, target, combination):
if target == 0:
result.append(
combination[:]
) # Append a copy of the current combination
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue # Skip duplicates at the same depth level
if candidates[i] > target:
continue # Skip if the candidate is too large
combination.append(candidates[i])
backtrack(i + 1, target - candidates[i], combination)
combination.pop() # Backtrack
candidates.sort() # Sort the input to handle duplicates
result = []
backtrack(0, target, [])
return result