Two coins of each kind (3)

Go to the Jutge statement of the problem

Given a 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 equal.

For example, if x = 4 and the available values are 1 and 2, then there are two ways to achieve it: 1 + 1 + 2 and 2 + 2. As another example, if x = 5 and the available values are 1, 2, 3, 4 and 5, then there are five ways: 1 + 1 + 3, 1 + 2 + 2, 1 + 4, 2 + 3 and 5.

Input: Input consists of several cases, with only integer numbers. Every case begins with x and n, followed by c_1 \dots c_n. Assume 1 \leq n \leq 15, 1 \leq c_i \leq x \leq 10^6, and that all c_i are different.

Output: For every case print the number of different ways to achieve change exactly x by using each value at most twice.

A simply pruned backtracking should be enough.

Hint

The exercise asks to compute the size of the set

A=\left\{(b_0,\dots,b_{n-1})\in \{0,1,2\}^n : \sum_{i=0}^{n-1} b_i c_i =x\right\}\ , where c_0, …, c_{n-1} and x are as in the problem statement.

Let A_{s,k} be the set

A_{s,k}=\left\{(b_k,\dots,b_{n-1})\in \{0,1,2\}^n : s+\sum_{i=k}^{n-1} b_i c_i =x\right\}\ ,

In other words, since A=A_{0,0} we want to compute |A_{0,0}|. Notice that

A_{s,k} = A_{s,k+1} \cup A_{s+c_k, k+1} \cup A_{s+2c_k, k+1}\ . Since the sets are disjoint then

|A_{s,k}| = |A_{s,k+1}| + |A_{s+c_k, k+1}| + |A_{s+2c_k, k+1}|\ .

Moreover, |A_{s,k}| =0 whenever s> x, and |A_{s,n}|=1 if s=x and otherwise |A_{s,n}|=0.

Use the facts above to construct a function int backtracking(int k, int s) that computes |A_{s,k}|.

A possible C++ code to start the problem

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

using namespace std;

int x, n;
vector<int> coins;//eventually n will be coins.size()

int bt(int k, int part_sum){
    // backtracking 
}

int main(){
    while (cin >> x >> n){
        coins = vector<int>(n);
        for (int i = 0; i < n; ++i)
            cin >> coins[i];
        cout << bt(0, 0) << endl;
    }
}

A possible solution

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

using namespace std;

int x, n;
vector<int> coins;//eventually n will be coins.size()

int bt(int k, int part_sum){
    if (part_sum > x) return 0;
    if (k == n) return part_sum == x;
    return (bt(k+1,part_sum) + bt(k+1, part_sum + coins[k]) + bt(k+1, part_sum + 2*coins[k]));
}

int main(){
    while (cin >> x >> n){
        coins = vector<int>(n);
        for (int i = 0; i < n; ++i)
            cin >> coins[i];
        cout << bt(0, 0) << endl;
    }
}

Other Links