Finding pairs that add up to a given sum, using recursion

Question

I'm currently tasked with using recursion to find pairs that add up to a given sum. How would I make the function recursiveFixedSumPairs function more efficient and truncate this code? Also, what is the current runtime? I believe it is n since it will go through the array only once always starting at the first index.

public class HW4 {

    public static void main(String[] args) {

        int[] a = {1, 5, 8, 11, 14, 15, 20, 23, 25, 28, 30, 34};
        int k;
        k = 43;
        System.out.println("k = " + k);
        findFixedSumPairs(a, k);
    }

    public static void findFixedSumPairs(int[] a, int k) {
       recursiveFixedSumPairs(a, -1, 0, k);
    }

    private static void recursiveFixedSumPairs(int[] array, int subPair1, int index, int k) {
//        // pairs whose sum equals k are printed in this method
//        if ((array[subPair1] + array[subPair2]) == k) {
//            System.out.println("[" + array[subPair1] + ", " + array[subPair2] + "]");
//        } else if ((array[subPair1] + array[subPair2]) > k) {
//            recursiveFixedSumPairs(array, subPair1, subPair2 - 1, k);
//        } else {
//            recursiveFixedSumPairs(array, subPair1 + 1, subPair2, k);
//        }

            if (index == array.length) {
                return;
            }

            else if (index == array.length-1) {

                if (subPair1!= -1 && subPair1 + array[index] == k) {
                    System.out.println(""+subPair1 +" "+ array[index]);
                }

                else {
                    return;
                }
            }

            if (subPair1 != -1) {

                if (array[index] == k- subPair1) {
                    System.out.println(""+subPair1 +" "+ array[index]);
                    return;
                } else {
                    recursiveFixedSumPairs(array, subPair1, index + 1, k);
                }

            } else {
                recursiveFixedSumPairs(array, array[index], index+1, k);
                recursiveFixedSumPairs(array,-1, index+1, k);
            }
        }
}

Answer 1

Recursion is about dividing and conquering. You are going to check the first element of an array (E0) against each element in the rest of the array. Once you have checked all the elements, you pick the next element (E1) in the array and check it against all the other elements. Since you've already checked E1 against E0 in the previous iteration, you only need to check E1 against the elements after it.

First of all, your naming is unclear. The "fixed" has no meaning here, so let's drop it. Single letter parameter and argiment names are only reserved for loop counters. So "k" must become "expectedSum". The entry-function to the iteration just takes the user input. It adds the initial entry parameters for the iterative function (indexes to first entry in the array and the first entry of the sub-array. Since the entry function initializes the recursive function with valid values, there is no need to check for magic -1 values in the iterative function anymore.

public static void findSumPairs(int[] array, int expectedSum) {
    recursiveSumPairs(array, expectedSum, 0, 1);
}

private static void recursiveSumPairs(
        int[] array,
        int expectedSum,
        int firstIndex,
        int nextIndex) {

    // End condition for recursion: first element to check is the last
    // element in the array. This also handles input arrays shorter than
    // two elements.
    if (firstIndex >= array.length - 1) {
        return;
    }

    // We have exhausted the sub-array. Advance the first element to the
    // next index and compare it to the rest of the elements left in the
    // array.
    if (nextIndex >= array.length) {
        recursiveSumPairs(array, expectedSum, firstIndex + 1, firstIndex + 2);
        return;
    }

    if (array[firstIndex] + array[nextIndex] == expectedSum) {
        System.out.println(array[firstIndex] + " + " + array[nextIndex]);
    }

    // Compare first element to the next element in the array.
    recursiveSumPairs(array, expectedSum, firstIndex, nextIndex + 1);
}

My presonal preference is to use ">=" and "<=" instead of "==" when checking loop counters against end conditions. It implies that the left side of the comparison is a value that increases/decreases and guards against bugs where the counter increases by two. Although if you were really paranoid you could add special check for that and throw an IllegalStateException (the new kids on the block would probably use assertations).

Now, if you want to go fancy with the solution, instead of burdening the algorithm with display functions (System.out.printlning the result), you could pass a BiConsumer to the function and let the caller decide what to do with the results (possibly with a nice lambda).

findSumPairs(
    array,
    sum,
    (a, b) -> System.err.println(a + " + " + b));