All possible sum from a given of coins

Question

You have n coins with certain values. Your task is to find all the money sums you can create using these coins.

Input

The first input line has an integer n: the number of coins.

The next line has n integers x1,x2,…,xn: the values of the coins.

Output

First print an integer k: the number of distinct money sums. After this, print all possible sums in increasing order.

Constraints

1≤n≤100
1≤xi≤1000

Example

Input:

4
4 2 5 2

Output:

9
2 4 5 6 7 8 9 11 13

I have written a code which works perfectly for the small inputs but gives the wrong answer to the large inputs. Please help to find the mistake and how do I correct it.

my code is:

#include 
using namespace std;

set s;
// Prints sums of all subsets of array
void subsetSums(long long arr[], long long n)
{
    // There are totoal 2^n subsets
    long long total = 1 << n;

    // Consider all numbers from 0 to 2^n - 1
    for (long long i = 0; i < total; i++)
    {
        long long sum = 0;

        // Consider binary reprsentation of
        // current i to decide which elements
        // to pick.
        for (long long j = 0; j < n; j++)
            if (i & (1 << j))
                sum += arr[j];

        // Print sum of picked elements.
        if (sum)
            s.insert(sum);
    }
}

// Driver code
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n;
    cin >> n;
    long long arr[n];
    for (long long i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    subsetSums(arr, n);
    cout << s.size() << "
";
    for (auto it = s.begin(); it != s.end(); ++it)
        cout << *it << " ";
    return 0;
}

for example, it gives the wrong answer for

50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

as

18
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36

the correct output should be:

50
1 2 3 4 ... 50

user_4059145 · Answer

your code is simply too slow 2^n subsets gives ‭1,267,650,600,228,229,401,496,703,205,376‬ subsets in the worst case (when n=100) while C++ does on average about 1000,000,000 operations per second.

This problem can be solved with dynamic programming, consider having an array dp of size 100001, so that dp[x] denotes if sum of x is possible to achieve.

Base case is easy - sum of 0 is possible without using any coins: dp[0]=1

Then for each coin we can try to increase existing sums by coins value to fill up our table:

for each coinValue:
for coinSum = 100000 - coinValue; coinSum >=0; coinSum--)
    if(dp[coinSum])
    dp[coinSum + coinValue]=1

Notice that we are looping backwards, this is done on purpose so that each coin gets used only once.

Complexity: O(n^2*maxCoinValue)

user_1400793 · Answer

Your algorithm is poor, but the reason you're getting wrong results is because you're overflowing int. long long total = 1< shifts an int left by n places, and the fact you're assigning the result to a long long is irrelevant.



You can find problems like this using ubsan. Here's a reproduction of your problem, including warning messages from ubsan:

$ clang++ -fsanitize=undefined a.cpp -o a && ./a
50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
a.cpp:11:25: runtime error: shift exponent 50 is too large for 32-bit type 'int'
a.cpp:22:24: runtime error: shift exponent 32 is too large for 32-bit type 'int'
18
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36

All possible sum from a given of coins

2 Answers