DSA

Combination Sum II

Recursion & Backtracking. Time O(2<sup>n</sup>), Space O(n).

August 8, 2026

DSA Backtracking Recursion LeetCode Practice

Practice Here

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.

Approach#

Sort the candidates so duplicates are adjacent. At each index make two recursive calls: one that skips the current element, and one that picks it (if it doesn't exceed the remaining target). To avoid duplicate combinations, if the current element equals the previous one (nums[idx] == nums[idx-1]) and the previous element was NOT picked (!preTaken), skip the pick branch entirely — this ensures that two identical values produce only one distinct subset. Each element may be used at most once, so both branches always advance to idx+1.

cpp

class Solution {
public:
void combinationSumUtil(vector<int>& nums,vector<int>& temp, vector<vector<int>> &res, int target, int idx, bool preTaken)
    {
        if(idx==nums.size())
        {
            if(target==0){
                res.push_back(temp);
            }
            return;
        }

        combinationSumUtil(nums, temp, res, target, idx+1, false);

        if(idx>0 && nums[idx-1]==nums[idx] && !preTaken)
            return;

        if(nums[idx] <= target){
            temp.push_back(nums[idx]);
            combinationSumUtil(nums, temp, res, target-nums[idx], idx+1, true);
            temp.pop_back();
        }
        
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> uniqueCombinations;
        vector<int> temp;
        bool preTaken = false;
        combinationSumUtil(candidates, temp, uniqueCombinations, target, 0,preTaken );

        return uniqueCombinations;
    }
};

Time Complexity: O(2ⁿ), T -> target

Space Complexity: O(n)

DSAGenerate ParenthesesGenerate all combinations of well-formed parentheses using backtracking. Optimal — Time O(4ⁿ/√n), Space O(n).6 min read DSALetter Combinations of a Phone NumberMiscellaneous problem — solution with code and analysis.DSASudoku SolverCovers: Brute Force, Optimized Safe Check. Optimal — Time O(9^(number of empty cells), Space O(m*n).

Approach#

Related articles