Advertisement
Guest User

Untitled

a guest
Sep 25th, 2017
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.82 KB | None | 0 0
  1.  
  2. import java.util.*;
  3.  
  4. public class Main {
  5.  
  6.     public static void bruteForce(int sum, Long[] numbers, int[] currSum,
  7.             Vector<Integer> perm, HashSet<Vector<Integer>> results, int i, int k) {
  8.         if (currSum[0] == sum && !results.contains(perm)) {
  9.             Vector<Integer> temp = new Vector<Integer>(perm.size());
  10.             for (int l = 0; l < perm.size(); l++) {
  11.                 temp.add(l, perm.get(l));
  12.             }
  13.             results.add(temp);
  14.             String res = "";
  15.             if (perm.size() > 0) {
  16.                 res = perm.get(0) + "";
  17.                 for (int j = 1; j < perm.size(); j++) {
  18.                     res += "+" + perm.get(j);
  19.                 }
  20.             }
  21.             System.out.println(res);
  22.         } else
  23.             for (int j = k; j < numbers.length; j++)
  24.                 if (numbers[j] <= sum) {
  25.                     if (currSum[0] + numbers[j] <= sum) {
  26.                         Vector<Integer> temp = new Vector<Integer>(perm.size());
  27.                         for (int l = 0; l < perm.size(); l++) {
  28.                             temp.add(l, perm.get(l));
  29.                         }
  30.                         int temp2 = currSum[0];
  31.                         perm.add(numbers[j].intValue());
  32.                         bruteForce(sum, numbers, new int[] { currSum[0]
  33.                                 + numbers[j].intValue() }, perm, results,
  34.                                 i + 1, j + 1);
  35.                         perm = temp;
  36.                         currSum[0] = temp2;
  37.                     }
  38.                     if (j == numbers.length - 1 && i == 0
  39.                             && results.size() == 0)
  40.                         System.out.println("NONE");
  41.                 }
  42.     }
  43.  
  44.     public static void main(String[] args) {
  45.         Scanner myScanner = new Scanner(System.in);
  46.         int t = myScanner.nextInt();
  47.         int n = myScanner.nextInt();
  48.         Long[] numbers = new Long[n];
  49.         while (n > 0) {
  50.             for (int i = 0; i < n; i++) {
  51.                 numbers[i] = myScanner.nextLong();
  52.             }
  53.             Arrays.sort(numbers, Collections.reverseOrder());
  54.             System.out.println("Sums of " + t + ":");
  55.             bruteForce(t, numbers, new int[1], new Vector<Integer>(),
  56.                     new HashSet<Vector<Integer>>(), 0, 0);
  57.             t = myScanner.nextInt();
  58.             n = myScanner.nextInt();
  59.             numbers = new Long[n];
  60.         }
  61.     }
  62.  
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement