#include <iostream>
#include <vector>
#include <algorithm>
void findCombinations(int index, int target, std::vector<int>& vec,
std::vector<int>& current, std::vector<std::vector<int>>& result) {
if (target == 0) {
result.push_back(current);
return;
}
for (int i = index; i < vec.size(); ++i) {
if (i > index && vec[i] == vec[i - 1]) continue; // Skip duplicates
if (vec[i] > target) break; // No need to proceed further
current.push_back(vec[i]);
findCombinations(i + 1, target - vec[i], vec, current, result);
current.pop_back();
}
}
std::vector<std::vector<int>> combinationSumTo(std::vector<int>& vec, int target) {
std::sort(vec.begin(), vec.end()); // Sort to handle duplicates
std::vector<std::vector<int>> result;
std::vector<int> current;
findCombinations(0, target, vec, current, result);
return result;
}
int main() {
std::vector<int> vec = {4, 2, 7, 8, 3, 5, 1};
int target = 7;
std::vector<std::vector<int>> result = combinationSumTo(vec, target);
std::cout << "Unique combinations that sum to " << target << ":\n";
for (const auto& combination : result) {
for (int num : combination) {
std::cout << num << " ";
}
std::cout << "\n";
}
}
/*
run:
Unique combinations that sum to 7:
1 2 4
2 5
3 4
7
*/
