Untitled

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

void backtrack(const std::vector<int>& candidates, int target, std::vector<int>& combination, std::vector<std::vector<int>>& results, int start) {
    if (target == 0) {
        results.push_back(combination);
        return;
    }
    if (target < 0) {
        return;
    }
    for (int i = start; i < candidates.size(); i++) {
        if (candidates[i] > target) {
            break;
        }
        // Avoid duplicates by only considering elements starting from the current index
        if (i > start && candidates[i] == candidates[i-1]) {
            continue;
        }
        combination.push_back(candidates[i]);
        backtrack(candidates, target - candidates[i], combination, results, i);
        combination.pop_back();
    }
}

std::vector<std::vector<int>> combinationSum(std::vector<int>& candidates, int target) {
    std::vector<std::vector<int>> results;
    std::sort(candidates.begin(), candidates.end());  // Sort the array to handle duplicates efficiently
    std::vector<int> combination;
    backtrack(candidates, target, combination, results, 0);
    return results;
}

int main() {
    std::vector<int> candidates = {2, 3, 6, 7};
    int target = 7;
    std::vector<std::vector<int>> combinations = combinationSum(candidates, target);
    for (const auto& combination : combinations) {
        for (int num : combination) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}