Print all subsets in an array that equal to a given sum recursively

Question

I have to write a code with a two methods that takes an array (non-negative) and a value sum as parameters. I have to use the methods:

---

public static void printSubsetSums(int[] arr, int sum) {

}

public static void printSubsetSums(int[] arr, int sum, int i, String acc) 
{

}

---

We are not allowed to add methods or any more parameters for the current methods. I did something similar that just prints the number of subsets that are from a given array according to a sum. but i'm having a hard time to change it to do this task... my array is limited to the length of 5.

ecxample: "Enter 5 numbers to array" input:1 2 3 4 5 "Enter a number into sum" input:8 3

why 3? (3,5) , (1,3,4) , (1,2,5)

Thank you for your help!!!

Answer 1

The requirement imposed in the question is a little difficult to interpret. However, I have coded to fulfill your use case.

The approach which I have used is the following:

1. Find all the possible subset of the given array using the bit-manipulation method.

2. Check if the sum of the subset is equal to the given sum. If it is yes, then print it on the console.

Check the snippet below for more clarity.

import java.util.Scanner;

public class SubsetSum {
    public static void printSubsetSums(int[] arr, int sum) {
        printSubsetSums(arr, sum, 0, "NotNeeded");
    }

    public static void printSubsetSums(int[] arr, int sum, int i, String acc) {
        // variable 'i' and 'acc' are not getting used anywhere.
        // Have added because you want to make the same syntax for the function.
        boolean isAnySubsetPossible = false;
        int n = arr.length;

        // Run a loop from 0 to 2^n
        for (int p = 0; p < (1 << n); p++) {
            int[] temporaryArray = new int[n];
            int k = 0;
            int m = 1; // m is used to check set bit in binary representation.
            // Print current subset
            for (int j = 0; j < n; j++) {
                if ((p & m) > 0) {
                    temporaryArray[k++] = arr[j];
                }
                m = m << 1;
            }

            int localSum = 0;
            for (int temp : temporaryArray) {
                localSum += temp;
            }
            if (localSum == sum) { // check if the sum is equal to the desired sum
                isAnySubsetPossible = true;
                for (int item : temporaryArray) {
                    if (item > 0) {
                        System.out.print(item + " ");
                    }
                }
                // print a new line so that next subset starts from new line
                System.out.println();
            }
        }
        if (!isAnySubsetPossible) {
            System.out.println("There is no subset possible for the sum = " + 20);
        }
    }

    public static void main(String[] args) {
        Scanner myScanner = new Scanner(System.in);
        System.out.println("Enter 5 numbers into array");
        int[] myArr = new int[5];
        for (int i = 0; i < myArr.length; i++) {
            myArr[i] = myScanner.nextInt();
        }
        System.out.println("Enter a number into sum");
        int sum = myScanner.nextInt();
        printSubsetSums(myArr, sum);
    }
}

Input1 to the program

Enter 5 numbers into array
1 2 3 4 5
Enter a number into sum
8

Output1 by the program

1 3 4 
1 2 5 
3 5

Input2 to the program

Enter 5 numbers into array
1 2 3 4 5
Enter a number into sum
20

Output2 by the program

There is no subset possible for the sum = 20

I hope this helps.