for those who don't know sum of subset problem just google it.

But allow me to explain what is power set

e.g. let X be an set, X = { 1,2,3}

then power set will contain = 2^n subset of set X, where n is no. of elements in set X

so our power set will contain total 8 subset of set X

power set = { , {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} }

notice that the 1st set is a null set because a null set is a subset of every set.

Now consider sum of subset problem

let X be an array which contains input from user let X = {1,2,3}

then power set = { , {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} }

let m = 3

then the output of sum of subset problem is { {3},{1,2} }

if you are reading from beginning than now you must have a fair idea about what we are going to do, if you didn't understand than chill, the concept will be very clear in 5 minutes from now.

once we have computed the power set, we will take each individual set from the power set, if the power set contains only 1 element than we will compare that element with m if that element is equal to m than we will print that set as 1 of the solution, but if set contain multiple elements in it than we will add them all and compare the sum with m if it is equal than we will print the set. that's it!

###

But allow me to explain what is power set

e.g. let X be an set, X = { 1,2,3}

then power set will contain = 2^n subset of set X, where n is no. of elements in set X

so our power set will contain total 8 subset of set X

power set = { , {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} }

notice that the 1st set is a null set because a null set is a subset of every set.

Now consider sum of subset problem

let X be an array which contains input from user let X = {1,2,3}

then power set = { , {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} }

let m = 3

then the output of sum of subset problem is { {3},{1,2} }

if you are reading from beginning than now you must have a fair idea about what we are going to do, if you didn't understand than chill, the concept will be very clear in 5 minutes from now.

once we have computed the power set, we will take each individual set from the power set, if the power set contains only 1 element than we will compare that element with m if that element is equal to m than we will print that set as 1 of the solution, but if set contain multiple elements in it than we will add them all and compare the sum with m if it is equal than we will print the set. that's it!

### Program:

import java.util.ArrayList; import java.util.LinkedHashSet; import java.util.Scanner; import java.util.Set; //@author Naved Momin navedmomin10@gmail.com; public class SumOfSubsets { public ArrayListpowerSet(int a[]){ ArrayList pw = new ArrayList (); pw.add(" "); for (int i = 1; i <= a.length; i++) { ArrayList tmp = new ArrayList (); for (String e : pw) { if(e.equals(" ")) tmp.add(""+a[i-1]); else tmp.add(e+ " " + a[i-1]); } pw.addAll(tmp); } return pw; } int m ; public void navedsSOS( ArrayList p ){ int sum = 0; System.out.println( "output: "); for (String string : p) { String[] split = string.split(" "); if(split.length > 1){ for (String no : split) { sum += Integer.parseInt(no); } if( sum == m){ if(!set.contains(string)){ set.add(string); System.out.println( string ); } } sum = 0; }else if( split.length == 1){ int k = Integer.parseInt(string); if( k == m ){ if(!set.contains(string)){ System.out.println( " " + k ); set.add(string); } } } } } public static void main(String[] args) { // TODO code application logic here SumOfSubsets s = new SumOfSubsets(); s.init(); } int n ; int arr[]; Scanner s = new Scanner(System.in); Set set = new LinkedHashSet (); private void init() { System.out.println( "enter n "); n = s.nextInt(); System.out.println( "enter m "); m = s.nextInt(); arr = new int[n]; System.out.println( "enter elemets "); for (int i = 0; i < n; i++) { arr[i] = s.nextInt(); //set.add(arr[i]); } ArrayList powerSet = powerSet(arr); navedsSOS(powerSet); } }