40. Combination Sum II

📝 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 number target find all combinations in candidates where the candidate numbers sum to target each number in candidates 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();
        }
    }
};