#include <iostream>
#include <vector>
using namespace std;

void printKnapsack(const vector<int>& knapsack) {
    cout << "[";
    for (int x : knapsack)      // range for : x will be called for each int in the knapsack vector
        cout << x <<" ";
    cout<<"]"<<endl; 
}

void print_solutions(int current_item, vector<int>& knapsack, int current_sum, const vector<int>& items, int limit) {
    //if all items have been processed print the solution and return
    if (current_item == items.size() ) {
        printKnapsack(knapsack);
        return;
    };

    //don't take the current item and go check others
    vector<int> knapcopy = knapsack; 
    print_solutions(current_item + 1, knapcopy, current_sum, items, limit);

    //take the current item if the value doesn't exceed the limit
    if (current_sum + items[current_item] <= limit) {
        knapsack.push_back(items[current_item]);
        current_sum += items[current_item];
        //current item taken go check others
        print_solutions(current_item + 1, knapsack, current_sum, items, limit);
    };
};


int main() {
    int current_item = 0;
    int current_sum = 0;
    int limit, n;
    cout << "Type the maximum weight ";
    cin >> limit;
    cout << "How many items?  ";
    cin >> n;

    vector<int> knapsack;   // empty vector
    vector<int> items(n);   // vector with n elements

    cout << "Type weights.";
    for (int i = 0; i < n; i++) {
        cin >> items[i];
    };

    print_solutions(0, knapsack, 0, items, limit);  // n not needed

    return 0;

}