Thursday, 18 April 2019

Program to implement sum of subset problem in java without using recursion

Problem : Given a set of integers SET, and a value sum SUM, determine if there is a subset of the given set with sum equal to given sum.




In computer science, the subset sum problem is an important decision problem in complexity theory and cryptography. There are several equivalent formulations of the problem. One of them is: given a set (or multiset) of integers, is there a non-empty subset whose sum is zero? For example, given the set {\displaystyle {-7,-3,-2,5,8}}, the answer is yes because the subset {\displaystyle {-3,-2,5}} sums to zero. The problem is NP-complete, meaning roughly that while it is easy to confirm whether a proposed solution is valid, it may inherently be prohibitively difficult to determine in the first place whether any solution exists. --Wikipedia
SET = {1,-2,3,5,-4,6,7}
SUM= 19
SUBSET = {1, 5, 6, 7}, {-2, 3, 5, 6, 7}
/*
    Sum of Subset Problem
    Created By: Pirate
*/

import java.util.ArrayList;
import java.util.List;
public class SumofSubset {
    public static void main(String arg[]) {
        int set[] = {1,-2,3,5,-4,6,7};
        int sum = 19;
        List<List<Integer>> result = findSumOfSubset(set, 7, sum);
        System.out.println(result);
    }
    static List<List<Integer>> findSumOfSubset(int set[], int size, int sum) { 
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        long totalSet = (long)Math.pow(2, size); 
        int counter, j; 
        for(counter = 0; counter < totalSet; counter++) { 
            List<Integer> subSet = new ArrayList<Integer>();
            for(j = 0; j < size; j++) { 
                if((counter & (1 << j)) > 0) 
                    subSet.add(set[j]);
            } 
            list.add(subSet) ;
        }
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for(List<Integer> createdSet : list) {
            int sumOfElements = 0;
            for(Integer element : createdSet) {
                sumOfElements = sumOfElements + element;
            }
            if(sumOfElements == sum) {
                result.add(createdSet);
            }
        }
        return result;
    }   

}

Output : 
[[1, 5, 6, 7 ], [ -2, 3, 5, 6, 7 ]]