Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class Main {
- public static void bruteForce(int sum, Long[] numbers, int[] currSum,
- Vector<Integer> perm, HashSet<Vector<Integer>> results, int i, int k) {
- if (currSum[0] == sum && !results.contains(perm)) {
- Vector<Integer> temp = new Vector<Integer>(perm.size());
- for (int l = 0; l < perm.size(); l++) {
- temp.add(l, perm.get(l));
- }
- results.add(temp);
- String res = "";
- if (perm.size() > 0) {
- res = perm.get(0) + "";
- for (int j = 1; j < perm.size(); j++) {
- res += "+" + perm.get(j);
- }
- }
- System.out.println(res);
- } else
- for (int j = k; j < numbers.length; j++)
- if (numbers[j] <= sum) {
- if (currSum[0] + numbers[j] <= sum) {
- Vector<Integer> temp = new Vector<Integer>(perm.size());
- for (int l = 0; l < perm.size(); l++) {
- temp.add(l, perm.get(l));
- }
- int temp2 = currSum[0];
- perm.add(numbers[j].intValue());
- bruteForce(sum, numbers, new int[] { currSum[0]
- + numbers[j].intValue() }, perm, results,
- i + 1, j + 1);
- perm = temp;
- currSum[0] = temp2;
- }
- if (j == numbers.length - 1 && i == 0
- && results.size() == 0)
- System.out.println("NONE");
- }
- }
- public static void main(String[] args) {
- Scanner myScanner = new Scanner(System.in);
- int t = myScanner.nextInt();
- int n = myScanner.nextInt();
- Long[] numbers = new Long[n];
- while (n > 0) {
- for (int i = 0; i < n; i++) {
- numbers[i] = myScanner.nextLong();
- }
- Arrays.sort(numbers, Collections.reverseOrder());
- System.out.println("Sums of " + t + ":");
- bruteForce(t, numbers, new int[1], new Vector<Integer>(),
- new HashSet<Vector<Integer>>(), 0, 0);
- t = myScanner.nextInt();
- n = myScanner.nextInt();
- numbers = new Long[n];
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement