import java.util.Scanner;

public class SumOfSubsets {

    static void sumOfSub(int[] weights, int[] x, int s, int k, int r, int m) {
        x[k] = 1;
        if (s + weights[k] == m) {
            printSolutionVector(x, k);
        } else if (s + weights[k] + (k + 1 < weights.length ? weights[k + 1] : 0) <= m) {
            sumOfSub(weights, x, s + weights[k], k + 1, r - weights[k], m);
        }

        if ((s + r - weights[k] >= m) && (s + (k + 1 < weights.length ? weights[k + 1] : 0) <= 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();
    }
}







SumOfSub(s, k, r)
{
    // Generate left child
    x[k] = 1
    if (s + w[k] == m) then
        write(x[1 : k]) // Subset found
    else if (s + w[k] + w[k + 1] <= m) then
        SumOfSub(s + w[k], k + 1, r - w[k])
 
    // Generate right child and evaluate conditions
    if ((s + r - w[k] >= m) and (s + w[k + 1] <= m)) then
    {
        x[k] = 0
        SumOfSub(s, k + 1, r - w[k])
    }
}