fork(1) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class SubSet
  9. {
  10.  
  11. 	public static void main(String[] args)
  12. 	{
  13. 		Integer[] set = { 1, 5, 9, 2, 3 };
  14. 		List<List<Integer>> subsets = subsetsK(set, 16);
  15. 		for (List<Integer> subset : subsets)
  16. 		{
  17. 			System.out.println(subset);
  18. 		}
  19. 	}
  20.  
  21. 	static List<List<Integer>> subsetsK(Integer[] arr, int k)
  22. 	{
  23. 		int t = 0;
  24. 		for (int n : arr) t += n;
  25.  
  26. 		List<List<Integer>> subsets = new ArrayList<>();
  27. 		allSubsets(subsets, arr, new BitSet(arr.length), 0, 0, t - k);
  28. 		return subsets;
  29. 	}
  30.  
  31. 	public static void allSubsets(List<List<Integer>> subsets, Integer[] arr, BitSet off, int pos, int sum, int lim)
  32. 	{
  33. 		if(sum > lim) return;
  34.  
  35. 		if(pos == arr.length)
  36. 		{
  37. 			subsets.add(toSubset(arr, off));
  38. 			return;
  39. 		}
  40.  
  41. 		off.set(pos);
  42. 		allSubsets(subsets, arr, off, pos + 1, sum + arr[pos], lim);
  43.  
  44. 		off.clear(pos);
  45. 		allSubsets(subsets, arr, off, pos + 1, sum, lim);
  46. 	}
  47.  
  48. 	static List<Integer> toSubset(Integer[] arr, BitSet off)
  49. 	{
  50. 		List<Integer> ss = new ArrayList<>();
  51. 		for (int i = 0; i < arr.length; i++)
  52. 		{
  53. 			if (!off.get(i))
  54. 				ss.add(arr[i]);
  55. 		}
  56. 		return ss;
  57. 	}	
  58. }
  59.  
  60.  
Success #stdin #stdout 0.07s 2841600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[5, 9, 3]
[5, 9, 2]
[5, 9, 2, 3]
[1, 5, 9, 3]
[1, 5, 9, 2]
[1, 5, 9, 2, 3]
https://ideone.com/B8xDhd
language:
Java (HotSpot 12)
created:
6 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!