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.
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;
}
}
[[1, 5, 6, 7 ], [ -2, 3, 5, 6, 7 ]]
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.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 :