Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.Collections;
- import java.util.HashMap;
- import java.util.Scanner;
- /**
- * Given an array A of size N, finds all combinations of four elements in the array whose
- * sum is equal to K.
- * @param args
- */
- public class FindAllFourSumNumbers implements Comparable<FindAllFourSumNumbers> {
- private int first;
- private int second;
- private int third;
- private int fourth;
- private int[] m_arr;
- /**
- * A constructor function which stores four arguments in increasing order
- * @param args
- */
- public FindAllFourSumNumbers(int one, int two, int three, int four) {
- int[] temp = {one, two, three, four};
- Arrays.sort(temp);
- this.m_arr = temp;
- this.first = temp[0];
- this.second = temp[1];
- this.third = temp[2];
- this.fourth = temp[3];
- }
- /**
- * Getter function to get the array
- */
- public int[] getArr() {
- return this.m_arr;
- }
- /**
- * Making 2 objects equal so long as their m_arr contain the same elements
- */
- @Override
- public boolean equals(Object other) {
- if (other == null) {
- return false;
- }
- if (other == this) {
- return true;
- }
- if (!(other instanceof FindAllFourSumNumbers)) {
- return false;
- }
- FindAllFourSumNumbers otherObj = (FindAllFourSumNumbers) other;
- if (!Arrays.equals(this.getArr(), otherObj.getArr())) {
- return false;
- }
- return true;
- }
- /**
- * Overriding the hashCode method as well since equality was over-ridden
- */
- @Override
- public int hashCode() {
- return Arrays.hashCode(this.m_arr);
- }
- /**
- * Compares two objects by looking at the first element of their m_arr
- */
- @Override
- public int compareTo(FindAllFourSumNumbers other) {
- int[] myArr = this.getArr();
- int[] otherArr = other.getArr();
- for (int i = 0; i < myArr.length; i++) {
- int current = myArr[i];
- int toCompare = otherArr[i];
- if (current > toCompare) {
- return 1;
- } else if (current < toCompare) {
- return -1;
- }
- }
- return 0;
- }
- /**
- * Allows for the printing of the pair
- * @param args
- */
- public String toString() {
- return this.first + " " + this.second + " " + this.third + " " + this.fourth + " " + "$";
- }
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- //number of test cases
- int num = sc.nextInt();
- for (int t = 0; t < num; t++) {
- int n = sc.nextInt();
- int k = sc.nextInt();
- //prevents the need for rehashing
- HashMap<Integer, ArrayList<FindAllFourSumNumbers>> myMap = new HashMap<>(n);
- int[] storage = new int[n];
- for (int i = 0; i < n; i++) {
- storage[i] = sc.nextInt();
- }
- //generate all combinations of a + b + c + d and adding it to the hash map
- for (int i = 0; i < n; i++) {
- for (int j = i + 1; j < n; j++) {
- for (int l = j + 1; l < n; l++) {
- for (int m = l + 1; m < n; m++) {
- int a = storage[i];
- int b = storage[j];
- int c = storage[l];
- int d = storage[m];
- int sum = a + b + c + d;
- FindAllFourSumNumbers myPair = new FindAllFourSumNumbers(a, b, c, d);
- if (myMap.containsKey(sum)) {
- ArrayList<FindAllFourSumNumbers> current = myMap.get(sum);
- if (!current.contains(myPair)) {
- current.add(myPair);
- }
- } else {
- ArrayList<FindAllFourSumNumbers> newList = new ArrayList<>(n);
- newList.add(myPair);
- myMap.put(sum, newList);
- }
- }
- }
- }
- }
- ArrayList<FindAllFourSumNumbers> toPrint = myMap.get(k);
- if (toPrint != null) {
- //so that everything is in order
- Collections.sort(toPrint);
- for (int i = 0; i < toPrint.size(); i++) {
- FindAllFourSumNumbers current = toPrint.get(i);
- System.out.print(current.toString());
- }
- System.out.println(" ");
- } else {
- System.out.println(-1);
- }
- }
- sc.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement