Two coins of each kind (1)

Go to the Jutge statement of the problem

Given a natural number x and n different coin values c_1 \dots c_n, compute in how many ways it is possible to achieve change x by using each value at most twice. Here, two coins with the same value are considered different.

For example, if x = 4 and the available values are 1 and 2, then there are three ways to achieve it: 1 + 1^′ + 2, 1 + 1^′ + 2^′, and also 2 + 2^′.

Input: Input consists of several cases. Every case begins with x and n, followed by c_1 \dots c_n.
Assume 1 \leq n \leq 20, 1 \leq c_i \leq x \leq 1000, and that all c_i are different.

Output: For every case print, in lexicographic order, all possible ways to exactly achieve change x by using each value at most twice. Print every solution with its values sorted from small to big. In doing that, assume 1 < 1^′ < 2 < 2^′ < \cdots. Use 1p to print 1^′, etcetera. Print a line with 10 dashes - at the end of every case.

A simply pruned backtracking should be enough.

Hint

Use the usual strategy for backtracking.

To write the solutions in lexicographical order, one option would be to sort the coins…

A possible C++ code to start the problem

// Two coins of each kind (1)
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

using VI = vector<int>;

int x, n;
VI coins;

void write (const vector<bool> & v){
    // format output
}

void backtrack(vector<bool>& sol, int k, int part_sum){
 // put code here
}

int main(){
    while (cin >> x >> n){
        coins = VI(2*n);
        for (int i = 0; i < 2*n; i +=2){
            cin >> coins[i];
            coins[i+1] = coins[i];
        }
        // do something here?
        backtrack(sol, 0, 0);
        cout << "----------" << endl;
    }
}

A possible solution

// Two coins of each kind (1)
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

using VI = vector<int>;

int x, n;
VI coins;

void write (const vector<bool> & v){
    cout << x << " = ";
    bool first = true;
    for (size_t i = 0; i < v.size(); ++i){
        if (v[i] != 0){
            if (first) first = false;
            else cout << " + ";
            cout << coins[i];
            if (i%2 == 1) cout << 'p';
        }
    }
    cout << endl;
}

void backtrack(vector<bool>& sol, int k, int part_sum){
    int n = sol.size();
    if (part_sum > x) return;
    if (k == n){
        if (x == part_sum) write(sol);
    }
    else{
        sol[k] = true;
        backtrack(sol, k+1, part_sum + coins[k]);
        sol[k] = false;
        backtrack(sol, k+1, part_sum);
    }
}

int main(){
    while (cin >> x >> n){
        coins = VI(2*n);
        for (int i = 0; i < 2*n; i +=2){
            cin >> coins[i];
            coins[i+1] = coins[i];
        }
        sort(coins.begin(),coins.end());
        vector<bool> sol(2*n, false);
        backtrack(sol, 0, 0);
        cout << "----------" << endl;
    }
}

Other Links