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 Ideone
  9. {
  10. 	List<List<Integer>> sodaPacks(int[] packs, int n, int i) {
  11. 		List<List<Integer>> result = new ArrayList<>();
  12.  
  13. 	  // Base case: we have one way to make an empty list
  14. 	  if (n == 0) {
  15. 	  	result.add(new ArrayList<>());
  16. 	  	return result;
  17. 	  }
  18.  
  19. 	  // Recursive step: we solve a smaller problem
  20. 	  // For each coin, you either include it or exclude it
  21. 	  // Include it:
  22. 	  if (n - packs[i] >= 0) {
  23. 		  List<List<Integer>> include = sodaPacks(packs, n - packs[i], i);
  24. 		  // If we include it, we must tack it on:
  25. 		  for (List<Integer> list : include) {
  26. 	        // Tack on our solution:
  27. 	        list.add(packs[i]);
  28. 	        result.add(list);
  29. 	      }
  30. 	  }
  31. 	  // Exclude it:
  32. 	  if (i + 1 < packs.length) {
  33. 		  List<List<Integer>> exclude = sodaPacks(packs, n, i + 1);
  34. 		  result.addAll(exclude);
  35. 	  }
  36. 	  return result;
  37. 	}
  38.  
  39. 	public static void main (String[] args) throws java.lang.Exception
  40. 	{
  41. 		Scanner sc = new Scanner(System.in);
  42. 		int n = sc.nextInt();
  43. 		int[] a = new int[n];
  44. 		for (int i = 0; i < n; i++) {
  45. 			a[i] = sc.nextInt();
  46. 		}
  47. 		int sodas = sc.nextInt();
  48. 		Ideone solution = new Ideone();
  49. 		System.out.println(solution.sodaPacks(a, sodas, 0));
  50. 		sc.close();
  51. 	}
  52. }
Success #stdin #stdout 0.14s 321344KB
comments (?)
stdin
copy 
4
1 2 3 5
5
stdout
copy 
[[1, 1, 1, 1, 1], [2, 1, 1, 1], [3, 1, 1], [2, 2, 1], [3, 2], [5]]
https://ideone.com/Ojnex0
language:
Java (HotSpot 12)
created:
8 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!