Revision history [back]

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