Program to implement sum of subset problem in java without using recursion | Wave the world

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 ]]



1 comments:

  1. <Investing online has been a main source of income, that's why knowledge plays a very important role in humanity, you don't need to over work yourself for money.All you need is the right information, and you could build your own wealth from the comfort of your home!Binary trading is dependent on timely signals, assets or controlled strategies which when mastered increases chance of winning up to 90%-100% with trading. It’s possible to earn $10,000 to $20,000 trading weekly-monthly in cryptocurrency(bitcoin) investment,just get in contact with Mr Bernie Doran my broker. I had almost given up on everything and even getting my lost funds back, till i met with him, with his help and guidance now i have my lost funds back to my bank account, gained more profit and I can now trade successfully with his profitable strategies and software!! 
Reach out to him through Gmail : Bernie.doranfx01@gmail.com ,Telegram: bernie_fx or WhatsApp +1(424)285-0682 for inquires

    ReplyDelete

 

Pro

About