import java.util.Scanner;
 
public class SumOfSubsets {
 
    static void sumOfSub(int[] weights, int[] x, int s, int k, int r, int m) {
    // 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 < weights.length && s + weights[k] + weights[k + 1] <= m) {
        sumOfSub(weights, x, s + weights[k], k + 1, r - weights[k], m);
    }

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

 
    static void printSolutionVector(int[] x, int k) {
        System.out.print("Solution Vector: ");
        for (int i = 0; i <=k; i++) {
            System.out.print(x[i] + " ");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        System.out.print("Enter the number of elements in the set: ");
        int n = scanner.nextInt();
 
        int[] weights = new int[n];
 
        System.out.println("Enter the elements of the set (in non-decreasing order): ");
        for (int i = 0; i < n; i++) {
            weights[i] = scanner.nextInt();
        }
 
        System.out.print("Enter the target sum (m): ");
        int m = scanner.nextInt();
 
        int[] x = new int[n];
        int r = 0;
        for (int weight : weights) {
            r += weight;
        }
 
        System.out.println("Solution Vectors with sum " + m + ":");
        sumOfSub(weights, x, 0, 0, r, m);
 
        scanner.close();
    }
}