Equal sums (3)

Go to the Jutge statement of the problem

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

Input: Input consists of a natural number s, followed by a number n > 0, followed by x_1, \dots , x_n.

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

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

Hint

This is the same as Equal sums (1) we saw few moments ago. The only difference is that now a very simple algorithm can be too slow. We have to do some pruning.

To get an idea of some pruning that might be useful, think on the input

5
5
1 1 1 1 1

Suppose you are exploring a branch were you chose the first 1 but not the second. Can this be completed to a full solution? Why?

A possible C++ code to start the problem

//Equal sums (3)

#include<iostream>
#include<vector>
#include<string>

using namespace std;

int n,s;
vector<int> x;

void write(const vector<bool>& sol){
    // function to write and format output
}

void bt(int k, ...more parameters...){
    // do the backtracking here
}

int main(){
    cin >> s >> n;
    x = vector<int>(n);
    for (int i = 0; i< n; ++i){
        cin >> x[i];
        // perhaps compute something else too?
    }
    // some backtracking
    bt(0, ...more parameters...);
}

A possible solution

//Equal sums (3)

#include<iostream>
#include<vector>
#include<string>

using namespace std;

int n,s;
vector<int> x;

void write(const vector<bool>& sol){
    int n = sol.size();
    cout << "{";
    string aux = "";
    for (int i = 0; i < n; ++i){
        if (sol[i]){
            cout << aux << x[i];
            aux = ",";
        }
    }
    cout << "}" << endl;
}

void bt(int k, vector<bool>& sol, int part_sum, int rest_sum){
    if (part_sum > s or part_sum + rest_sum < s) return;
    if (k == n){
        if (part_sum == s) write(sol);
    }
    else{
        sol[k] = false;
        bt(k+1, sol, part_sum, rest_sum - x[k]);
        sol[k] = true;
        bt(k+1, sol, part_sum + x[k], rest_sum - x[k]);
    }
}

int main(){
    cin >> s >> n;
    x = vector<int>(n);
    int sum = 0;
    for (int i = 0; i< n; ++i){
        cin >> x[i];
        sum += x[i];
    }
    vector<bool> sol(n,true);
    bt(0, sol, 0, sum);
}

Other Links