Combination Sum II medium

Problem Statement

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.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [[1,1,6],[1,2,5],[1,7],[2,6]] Explanation: 1 + 1 + 6 = 8 1 + 2 + 5 = 8 1 + 7 = 8 2 + 6 = 8

Example 2:

Input: candidates = [2,5,2,1,2], target = 5 Output: [[1,2,2],[5]] Explanation: 1 + 2 + 2 = 5 5 = 5

Steps

1. Sort the input array: Sorting allows us to easily skip duplicate numbers and prevent generating duplicate combinations.

2. Backtracking: Use a recursive backtracking function to explore all possible combinations.

3. Base Cases:

   • If the current sum equals the target, add the current combination to the result.
   • If the current sum exceeds the target, backtrack (return).

4. Recursive Step:

   • For each candidate number:
     • If the candidate is already used in the current combination (this avoids duplicates from the original array), skip it.
     • Add the candidate to the current combination.
     • Recursively call the function with the updated sum and combination.
     • Remove the candidate from the current combination (backtracking step) to explore other possibilities.

Explanation

The core idea is to use backtracking to explore all possible combinations. Sorting ensures we avoid duplicates efficiently. The used array (though not strictly necessary with the sorted array and skipping of duplicates explained above, it provides a more transparent understanding of the backtracking algorithm and can improve efficiency in unsorted scenarios) tracks whether a candidate has been used in the current combination. The recursive calls systematically explore all possibilities, adding and removing candidates to build up combinations that sum to the target. We only add a combination to the results if it sums to the target.

Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> combination;
        vector<bool> used(candidates.size(), false); //Optional: Tracks usage to handle duplicates in unsorted input.

        sort(candidates.begin(), candidates.end()); //Sort for efficiency

        backtrack(candidates, target, 0, combination, result, used);
        return result;
    }

private:
    void backtrack(vector<int>& candidates, int target, int index, vector<int>& combination, vector<vector<int>>& result, vector<bool>& used) {
        if (target == 0) {
            result.push_back(combination);
            return;
        }
        if (target < 0 || index >= candidates.size()) {
            return;
        }

        //Skip duplicate numbers
        if (index > 0 && candidates[index] == candidates[index - 1] && !used[index-1]) return; //only skip if previous is not used


        //Include current number
        combination.push_back(candidates[index]);
        used[index] = true;  // Mark as used
        backtrack(candidates, target - candidates[index], index + 1, combination, result, used);

        //Exclude current number
        combination.pop_back();
        used[index] = false; //Unmark as used
        backtrack(candidates, target, index + 1, combination, result, used);

    }
};

int main() {
    Solution solution;
    vector<int> candidates = {10, 1, 2, 7, 6, 1, 5};
    int target = 8;
    vector<vector<int>> result = solution.combinationSum2(candidates, target);

    for (const auto& combination : result) {
        for (int num : combination) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

Complexity

• Time Complexity: O(2^N * K), where N is the number of candidates and K is the average length of a combination. In the worst case, we explore all possible subsets.
• Space Complexity: O(N * K) in the worst case, due to the recursive call stack and storing the resulting combinations. The space used by the used vector is O(N) which is less significant than the other factors.