C++: Combination Sum II

Thought Process

To solve the Combination Sum II problem, we use backtracking with duplicate handling. First, we sort the candidates array to group duplicates together. During the backtracking process, we skip duplicate elements to avoid redundant combinations. This ensures that we generate only unique combinations that sum up to the target. 

class Solution {
public:
    void backTrack(vector<vector<int>> &ans, vector<int> tmp, vector<int>& candidates, int target,int start){
    
        if(target<0)
            return;
        if(target==0){
            ans.push_back(tmp);
        }
        for(int i=start;i<candidates.size();i++){
            // To remove the duplicates, if current element is equal to previous element
            // then we will skip the iteration
            if(i>start && candidates[i]==candidates[i-1])
                continue;
    
            tmp.push_back(candidates[i]);
            backTrack(ans,tmp,candidates,target-candidates[i], i+1);
            tmp.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    
        sort(candidates.begin(),candidates.end());
        vector<vector<int>> ans;
        vector<int> tmp;
        backTrack(ans,tmp,candidates,target, 0);
        return ans;
    }
};

Code Complexity

Time Complexity: O(2n)

The algorithm explores all possible combinations of the candidates, leading to an exponential time complexity. Sorting adds an additional O(n log n), where 'n' is the size of the input.

Space Complexity: O(n)

The recursion stack depth is proportional to the size of the input('n'), and the temporary vector stores intermediate results.

Code copied!