Equal sums (1)

Go to the Jutge statement of the problem

Write a program that, given an integer number s and n integer numbers x_1, … , x_n, prints all the subsets (maybe with repeated numbers, but using every x_i at most once) whose sum is exactly s.

Input: An integer number s, followed by a number n > 0, followed by x_1, …, x_n.

Output: Print all the subsets whose sum is s that can be made up with x_1, …, x_n.

You can print in any order both the solutions and the elements inside each solution.

Hint

For this exercise, simple backtracking solutions are accepted. No optimizations/pruning are required.

A possible C++ code to start the problem

// Equal sums (1)
#include<iostream>
#include<vector>

using namespace std;
using VI = vector<int>;
using VB = vector<bool>;

void write(VB& sol, VI& values){
    // write here
}

void bt(int k, int part_sum,VB& sol, VI& values, int s){
    // a simple backtracking would work

}
int main(){
    int s, n;
    cin >> s >> n;
    VI values(n); 
    for (int i = 0; i < n; ++i){
        cin >> values[i];
    }
    VB sol(n);
    bt(0, 0, sol, values, s);
}

A possible solution

// Equal sums (1)
#include<iostream>
#include<vector>

using namespace std;
using VI = vector<int>;
using VB = vector<bool>;

void write(VB& sol, VI& values){
    int n = sol.size();
    cout << "{";
    bool first = true;
    for (int i = 0; i < n; ++i){
        if (sol[i]){
            cout << (first ? "" : ",") << values[i];
            first = false;
        }
    }
    cout << "}" << endl;
}

void bt(int k, int part_sum,VB& sol, VI& values, int s){
    int n = sol.size();
    if (k == n){
        if (part_sum == s) write(sol,values);
    }
    else{
        sol[k] = false;
        bt(k+1, part_sum, sol, values, s);
        sol[k] = true;
        bt(k+1, part_sum + values[k], sol, values, s);
    }

}
int main(){
    int s, n;
    cin >> s >> n;
    VI values(n); 
    for (int i = 0; i < n; ++i){
        cin >> values[i];
    }
    VB sol(n);
    bt(0, 0, sol, values, s);
}