Sum Of Subset (Using PowerSet)

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!

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 ArrayList powerSet(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);
    }
}

outout: