Find distinct combinations of four elements in an array that have a certain sum

Question

The task is: Given an array A of size N, find all combinations of four elements in the array whose sum is equal to a given value K.

The specific requirements are:

1. The combinations must be distinct
2. Each quadruple is separated by a delimiter "$", and must be printed in ascending order

Here are some test cases highlighting the points above:

• Case #1 - size of Array A: 5, K: 3, Array A: 0 0 2 1, Answer: 0 0 1 2 $

• Case #2 - size of Array A: 7, K: 23, Array A: 10 2 3 4 5 7 8, Answer: 2 3 8 10 $2 4 7 10 $3 5 7 8 $

---

I solved this task, but my solution involves a whole bunch of data structures...which may or may not be necessary. Additionally, at one point in time I generated all the possible combinations, which I think has a horrifying run-time of O(n⁴) :(

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();

    }

}

Lengthy, yes, but it is complete, and I have commented it to make it easier to understand.

Answer 1

Thanks for sharing the code.

You don't ask for certain things to look at so here is my general critic:

formal issues

comments

Comments should always say why the code is like it is. Your comment mostly repeat what the code expresses itself.

Especially you have comments to explain variables like this:

    //number of test cases
    int num = sc.nextInt();

why not giving them better names instead?

  int numberOfTestCases = sc.nextInt();

You have a comment which logically forms a block inside your main method. You could extract that block to a method with a name derived from the comment:

 Map<> myMap= createHashMapFromAllCombinationsOf(a, b, c, d);  

naming

Finding good names is the hardest part in software development. So always take extra time to carefully choose them.

naming conventions

It is good that you follow formal patterns of the Java Naming Conventions.

identifiers with explaining comments

When ever you feel you need a comment to explain an identifier name take another 5 minutes to find a better name that makes the comment obsolete.

single letter names

Avoid single letter names and abbreviations unless they are very common.

No Verbs in class names

classes are (kind of) pattern for objects So they should not have verbs in their names like FindAllFourSumNumbers. This would make a good method name, but not a class name. (would you agree with MoveThingsToSomeOtherPlace instead of Vehicle?)

You should have the usage of your identifiers in mind when looking for names. Therefore I'd suggest to rename the class to SumOfNumbers

solution

duplicated feature

you store your data twice, in an array and in separate variables. Choose one and omit the other.

complexity

IMHO the solution requires O(n⁴) but your solution is O(n⁵) because of the (unneeded) storage array that you fill before the actual calculation.

You could reduce the complexity for some special cases when you limit the loops up to k since any tuple containing k+x has a sum bigger than k.

know your tools

The if/else in your loops clutters the code a bit. You could avoid the if by using the Maps getOrDefault() method:

ArrayList<FindAllFourSumNumbers> current = myMap.getOrDefault(sum, new ArrayList<>());
 if (!current.contains(myPair)) {
    current.add(myPair);
 }
 myMap.put(sum, newList);

And since you implemented equals and hashcode you could even leave the uniqueness (and the sorting) to the JVM:

 Collection<FindAllFourSumNumbers> current = myMap.getOrDefault(sum, new TreeSet<>());
 current.add(myPair);
 myMap.put(sum, newList);

---

1) does the fact that I stored it again in separate variables add to any costs? – umop apisdn

The obvious answer is: yes, since it uses extra memory.

The not so obvious answer is: I don't know (and don't care) since the JVM may (or may not) do some optimization to deal with that.

The point is: it confuses the reader.

---

I did that because I thought it might help with clarity since I won't have to keep doing storage[0], storage[1] etc. – umop apisdn

This reasoning is perfectly valid.

But on the other hand you only use the distinct variables in the toString() method. This could also be written this way:

public String toString() {  
  return Arrays.toString(m_array);  // add "[]" around the values
}

Then the distinct variables would be obsolete.

---

2) can you give more hints on how to work on the calculations directly without storing into an array? – umop apisdn

You mean something like you're doing here?

 int sum = a + b + c + d;

---

Also, how did you get O(n^5) for my solution...shouldn't it be O(n^4 + n + n choose 4) ~ O(n^4) ? thanks! – umop apisdn

Here I might be wrong, because only nested loops contribute exponents to the complexity.

But you definitely do not need the storage array and the loop to fill it.

ie.: if your loop variables are

i = 0;
j = 3;
l = 5;
m = 7;

what are the values you get in a, b, c and d?

And this is the best advice to improve performance I've ever ben given:

The fastest way to do something is not to do it.