π Problem Details
- Title:
40. Combination Sum II
- Link: https://leetcode.com/problems/combination-sum-ii/
- Difficulty: Medium
- Tags/Categories: Backtracking Sorting
given a vector of
candidates
and a target numbertarget
find all combinations incandidates
where the candidate numbers sum to target each number incandidates
can only be used once in the combination solution set cannot contain duplicate combinations
πWhat Were My Initial Thoughts?
- enumeration problem : find all possible combinations of candidates that sum to target
- choices: include or exclude candidates[i] in a subset
- constraints:
- combinations must be unique
- candidates cannot repeat inside a given subset
π€What Did I Struggle With?
- i assumed that the elements in candidates were distinct / unique similar to the previous questions
- initial submission did not account for duplicate elements
π‘ Explanation of Solution
- similar in approach to Combination Sum I
- sort the candidates vector prior to computation
- inside the DFS prune duplicate elements (we cna identify them as they will be adjacent to each other)
β Complexity Analysis
Time Complexity: O(2^n)
Space Complexity: O(2^n)
π» Implementation of Solution
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> currentSubset;
vector<vector<int>> result;
sort(candidates.begin(), candidates.end()); // Sort to handle duplicates
dfs(candidates, currentSubset, result, 0, target);
return result;
}
void dfs(vector<int>& candidates,
vector<int>& currentSubset,
vector<vector<int>>& result,
int index,
int target) {
// base case: if target == 0 then we have found a subset
if(target == 0) {
result.push_back(currentSubset);
return;
}
// explore
for(int i = index; i < candidates.size(); i++) {
if(candidates[i] > target) continue; // prune path
// skip duplicates
if(i > index && candidates[i] == candidates[i - 1]) continue;
// choose
currentSubset.push_back(candidates[i]);
// explore
dfs(candidates, currentSubset, result, i+1, target-candidates[i]);
// backtrack (undo the choice)
currentSubset.pop_back();
}
}
};