Money Sums

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

Example:

Input:  n = 4, a = {4, 2, 5, 2}

Output:

9
2 4 5 6 7 8 9 11 13 

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5 + 1;

vector<int> moneySums(int n, vector<int> &a)
{

    vector<bool> dp(MAX_N + 1);
    dp[0] = true;
    for (int i = 0; i < n; i++)
    {
        for (int j = MAX_N - 1; j >= a[i]; j--)
        {
            dp[j] = dp[j] | dp[j - a[i]];
        }
    }
    int ans = 0;
    for (int i = 1; i < MAX_N; i++)
        ans += dp[i];
    vector<int> res;
    res.push_back(ans);
    for (int i = 1; i < MAX_N; i++)
    {
        if (dp[i] == true)
            res.push_back(i);
    }
    return res;
}

int main()
{
    int n = 4;

    vector<int> a = {4, 2, 5, 2};
    vector<int> res = moneySums(n, a);

    cout << res[0] << "\n";

    for (int i = 1; i < res.size(); i++)
        cout << res[i] << " ";

    return 0;
}