#include <stdio.h>

void SumOfSub(int s, int k, int r, int w[], int n, int x[]) {
    // Base case: if the sum of weights equals the target
    if (s == r) {
        printf("Subset found: { ");
        for (int i = 0; i < k; i++) {
            if (x[i] == 1) {
                printf("%d ", w[i]);
            }
        }
        printf("}\n");
        return;
    }

    // If we exceed the number of weights or if the sum exceeds the target
    if (k >= n || s > r) {
        return;
    }

    // Generate left child: include current weight
    x[k] = 1; // Include w[k]
    SumOfSub(s + w[k], k + 1, r, w, n, x);

    // Generate right child: exclude current weight
    x[k] = 0; // Exclude w[k]
    SumOfSub(s, k + 1, r, w, n, x);
}

int main() {
    int n;
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    
    int w[n];
    printf("Enter the elements (non-decreasing order): ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &w[i]);
    }
    
    int m;
    printf("Enter the target sum: ");
    scanf("%d", &m);

    int x[n]; // Array to store inclusion/exclusion of weights
    SumOfSub(0, 0, m, w, n, x); // Start with sum 0 and index 0

    return 0;
}
INPUT:
Enter the number of elements: 5
Enter the elements (non-decreasing order): 1 2 3 4 5
Enter the target sum: 5
OUTPUT:
Subset found: { 1 4 }
Subset found: { 2 3 }
Subset found: { 5 }

import java.util.Scanner;

public class Main {

    // Method to find all subsets with sum equal to the target sum
    public static void SumOfSub(int s, int k, int r, int[] w, int n, int[] x) {
        // Base case: if the sum of weights equals the target
        if (s == r) {
            System.out.print("Subset found: { ");
            for (int i = 0; i < k; i++) {
                if (x[i] == 1) {
                    System.out.print(w[i] + " ");
                }
            }
            System.out.println("}");
            return;
        }

        // If we exceed the number of weights or if the sum exceeds the target
        if (k >= n || s > r) {
            return;
        }

        // Generate left child: include current weight
        x[k] = 1; // Include w[k]
        SumOfSub(s + w[k], k + 1, r, w, n, x);

        // Generate right child: exclude current weight
        x[k] = 0; // Exclude w[k]
        SumOfSub(s, k + 1, r, w, n, x);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Input for number of elements
        System.out.print("Enter the number of elements: ");
        int n = scanner.nextInt();

        // Input for the elements (weights)
        int[] w = new int[n];
        System.out.print("Enter the elements (non-decreasing order): ");
        for (int i = 0; i < n; i++) {
            w[i] = scanner.nextInt();
        }

        // Input for the target sum
        System.out.print("Enter the target sum: ");
        int m = scanner.nextInt();

        // Array to store inclusion/exclusion of weights
        int[] x = new int[n];

        // Start the recursion
        SumOfSub(0, 0, m, w, n, x);

        // Close the scanner
        scanner.close();
    }
}