Sure, here's an example program:
#include <iostream>
#include <vector>
#include <algorithm>
void printSums(const std::vector<int>& nums, int target, std::vector<int>& path, int start) {
if (target == 0) {
std::sort(path.begin(), path.end());
for (int i = 0; i < path.size(); i++) {
std::cout << path[i] << " ";
}
std::cout << std::endl;
return;
}
for (int i = start; i < nums.size(); i++) {
if (i > start && nums[i] == nums[i - 1]) {
continue; // skip duplicates
}
if (nums[i] > target) {
break; // can't use larger numbers
}
path.push_back(nums[i]);
printSums(nums, target - nums[i], path, i + 1);
path.pop_back();
}
}
int main() {
std::vector<int> nums = {1, 2, 2, 3, 4};
int target = 5;
std::vector<int> path;
std::sort(nums.begin(), nums.end()); // sort to handle duplicates
printSums(nums, target, path, 0);
return 0;
}
This program takes an input array of integers nums
, a target sum target
, and recursively computes all possible combinations of numbers that add up to the target sum, while accounting for duplicates.
The printSums
function recursively builds up a path of numbers that add up to the target sum, and prints out each valid path it finds. It uses a start
parameter to avoid reusing numbers that have already been considered.
The main
function initializes the input array and target sum, sorts the input array to handle duplicates, and calls printSums
to compute all possible sums.
When run with the input nums = {1, 2, 2, 3, 4}
and target = 5
, the program outputs the following:
1 2 2
1 4
2 3
Please start posting anonymously - your entry will be published after you log in or create a new account. This space is reserved only for answers. If you would like to engage in a discussion, please instead post a comment under the question or an answer that you would like to discuss
Asked: 2023-06-30 14:30:49 +0000
Seen: 9 times
Last updated: Jun 30 '23
What does an empty name signify in the inotify_event structure in the C++ language?
What is the method to get a printable output of a C++11 time_point?
What are the differences between TREEFROG, CROW, and the CPPCMS C++ framework?
How can the NTP flag be set for Linux time in C++?
What is the process of redefining a c++ macro with fewer parameters?
What are some other options instead of Scipy to compute CubicSpline?
How can a list be sorted alphabetically within a console application?