bank.cpp

#include <iostream>

using namespace std;

const int MAX_INT = ~(1 << (sizeof(int) * 8 - 1));

int main(){

    int n, sum;
    cin >> n;
    int value[100];
    for (int i = 0; i < n; i++){
        cin >> value[i];
    }
    cin >> sum;
    int *count = new int[sum + 1];
    count[0] = 0;

    for (int i = 1; i <= sum; i++){
        count[i] = MAX_INT;
        for (int j = 0; j < n; j++){
            if (i >= value[j])
                if (count[i] > count[i - value[j]] + 1)
                    count[i] = count[i - value[j]] + 1;
        }
    }
    if (count[sum] == MAX_INT)
        cout << "No solution";
    else{
        while (sum > 0){
            for (int i = 0; i < n; i++){
                if (sum >= value[i] && count[sum - value[i]] == (count[sum] - 1)){
                    cout << value[i] << " ";
                    sum -= value[i];
                    break;
                }
            }
        }
    }
    cout << endl;

    delete [] count;

    return 0;
}