Problem Statement

Given collection of candidate numbers (candidates) and a integer target. Find all unique combinations in candidates where the sum is equal to the target .There can only be one usage of each number in the candidates combination and return the answer in sorted order.

e.g., : The combination [1, 1, 2] and [1, 2, 1] are not unique.

Examples

Example 1:

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

Explanation:
The combinations whose sum is equal to the target are:
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:
The combinations whose sum is equal to the target are:
1 + 2 + 2 = 5
5 = 5

Example 3:

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

Explanation: The combination whose sum is equal to the target are:
1 + 2 + 2 = 5

Different Approaches

1️⃣ Recursion

Dry Run:

Let's dry run the following input:

candidates = [10, 1, 2, 7, 6, 1, 5], target = 8

After sorting, the candidates array becomes: [1, 1, 2, 5, 6, 7, 10].

Iteration 1:

• Start with the first element: 1
  • Add 1, remaining target = 8 - 1 = 7
  • Try the next element 1 again (because duplicates are allowed at the same position in the sorted array)
    • Add 1, remaining target = 7 - 1 = 6
    • Try next element 2
      • Add 2, remaining target = 6 - 2 = 4
      • Try next element 5
        • Add 5, remaining target = 4 - 5 = -1 (invalid, backtrack)
      • Backtrack and try 6
        • Add 6, remaining target = 4 - 6 = 0 (valid combination: [1, 1, 6])
        • Add this to the result and backtrack.

Iteration 2:

• Start with the second element 1:
  • Skip this as it's a duplicate of the previous 1 (index 0).

Iteration 3:

• Start with the third element: 2
  • Add 2, remaining target = 8 - 2 = 6
  • Try next element 5
    • Add 5, remaining target = 6 - 5 = 1
    • Try next element 6
      • Add 6, remaining target = 1 - 6 = -1 (invalid, backtrack)
    • Backtrack and try 7
      • Add 7, remaining target = 6 - 7 = 0 (valid combination: [1, 2, 5]).

And so on, until all possible combinations are explored.

Output:

[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

Code With For Loop:

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

using namespace std;

class Solution {
public:
    void backtrack(vector<int>& candidates, int target, vector<int>& currentCombination, vector<vector<int>>& result, int start) {
        // Base case: if the target becomes zero, we have found a valid combination
        if (target == 0) {
            result.push_back(currentCombination);
            return;
        }

        // Iterate over the candidates starting from the 'start' index
        for (int i = start; i < candidates.size(); i++) {
            // Skip duplicates (i.e., when the same element appears consecutively in the sorted list)
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            
            // If the current element exceeds the target, stop further exploration (since the array is sorted)
            if (candidates[i] > target) {
                break;
            }

            // Include the current candidate
            currentCombination.push_back(candidates[i]);

            // Recur with the remaining target and move to the next element (i + 1 ensures no reuse)
            backtrack(candidates, target - candidates[i], currentCombination, result, i + 1);

            // Backtrack: remove the last added element and try other candidates
            currentCombination.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> currentCombination;

        // Sort the candidates to handle duplicates and make the backtracking easier
        sort(candidates.begin(), candidates.end());

        // Start the backtracking process
        backtrack(candidates, target, currentCombination, result, 0);

        return result;
    }
};

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);

    // Output the result
    cout << "Unique combinations that sum to " << target << ":\n";
    for (const auto& combination : result) {
        cout << "[ ";
        for (int num : combination) {
            cout << num << " ";
        }
        cout << "]\n";
    }

    return 0;
}

Code Without For Loop:

class Solution {
public:
    void solve(vector<vector<int>>& result, vector<int>& candidates, vector<int>& output, int index, int target) {
        
        // Base Case: Target is met
        if (target == 0) {
            result.push_back(output);
            return;
        }
        
        // Base Case: Exceeded target or reached end of candidates
        if (target < 0 || index >= candidates.size()) {
            return;
        }

        // Option 1: Include the current candidate
        output.push_back(candidates[index]);
        solve(result, candidates, output, index + 1, target - candidates[index]);
        output.pop_back(); // Backtrack

        // Option 2: Exclude the current candidate and move to the next unique candidate
        int nextIndex = index + 1;
        while (nextIndex < candidates.size() && candidates[nextIndex] == candidates[index]) {
            nextIndex++;
        }
        solve(result, candidates, output, nextIndex, target);
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        // Sort candidates to handle duplicates
        sort(candidates.begin(), candidates.end());

        vector<vector<int>> result;
        vector<int> output;

        solve(result, candidates, output, 0, target);
        return result;
    }
};