fork(3) download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class SubsetSum
  6. {
  7. 	public static <T> Set<Set<T>> powerSet(Set<T> originalSet)
  8. 	{
  9.     	Set<Set<T>> sets = new HashSet<Set<T>>();
  10.     	if (originalSet.isEmpty()) 
  11.     	{
  12.     		sets.add(new HashSet<T>());
  13.     		return sets;
  14. 	 	}
  15.     	List<T> list = new ArrayList<T>(originalSet);
  16.     	T head = list.get(0);
  17.     	Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
  18.     	for (Set<T> set : powerSet(rest))
  19.     	{
  20.     		Set<T> newSet = new HashSet<T>();
  21.     		newSet.add(head);
  22.     		newSet.addAll(set);
  23.     		sets.add(newSet);
  24.     		sets.add(set);
  25.     	}		
  26.     	return sets;
  27. 	}
  28.  
  29.     public static void main(String[] args)
  30.     {
  31.  		Set<Integer> mySet = new HashSet<Integer>();
  32.  		int[] arr={3, 5, 5, 7};
  33.  		int target = 10;
  34.  		int numVals = 4;
  35.  		for(int i=0;i<numVals;++i)
  36.  		{
  37.  			mySet.add(i);
  38.  		}
  39.  		System.out.println("Solutions: ");
  40.  		for (Set<Integer> s : powerSet(mySet)) 
  41.  		{
  42.  			int sum = 0;
  43.  			for (Integer e : s)
  44.  			{
  45.  				sum += arr[e];
  46.  			}
  47.  			if (sum == target)
  48.  			{
  49.  				String soln = "[ ";
  50.  				for (Integer e : s)
  51.  				{
  52.  					soln += arr[e];
  53.  					soln += " ";
  54.  				}
  55.  				soln += "]";
  56.  
  57.  				System.out.println(soln);
  58.  			}
  59.  		}
  60.     }
  61. }
Success #stdin #stdout 0.1s 320320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Solutions: 
[ 5 5 ]
[ 3 7 ]
https://ideone.com/2Zs8bC
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!