#include <stdio.h>

void printSolutionVector(int* x, int k) {
    printf("Solution Vector: ");
    for (int i = 0; i <= k; i++) {
        printf("%d ", x[i]);
    }
    printf("\n");
}

void sumOfSub(int* weights, int* x, int s, int k, int r, int m, int n) {
    // Include the current element
    x[k] = 1;
    if (s + weights[k] == m) {
        // If the sum matches the target, print the solution vector
        printSolutionVector(x, k);
    } 
    // Check if including the current element and the next one keeps the sum within bounds
    else if (k + 1 < n && s + weights[k] + weights[k + 1] <= m) {
        sumOfSub(weights, x, s + weights[k], k + 1, r - weights[k], m, n);
    }

    // Exclude the current element and check if further exploration is valid
    if ((s + r - weights[k] >= m) && (k + 1 < n && s + weights[k + 1] <= m)) {
        x[k] = 0;
        sumOfSub(weights, x, s, k + 1, r - weights[k], m, n);
    }
}

int main() {
    int n;
    printf("Enter the number of elements in the set: ");
    scanf("%d", &n);

    int weights[n];
    printf("Enter the elements of the set (in non-decreasing order): ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &weights[i]);
    }

    int m;
    printf("Enter the target sum (m): ");
    scanf("%d", &m);

    int x[n];
    int r = 0;
    for (int i = 0; i < n; i++) {
        r += weights[i];
    }

    printf("Solution Vectors with sum %d:\n", m);
    sumOfSub(weights, x, 0, 0, r, m, n);

    return 0;
}