Tough recursive task

Question

I've been struggle with question I'm trying to solve as part of test preparation, and I thought I could use your help. I need to write a Boolean method that takes array with integers (positive and negative), and return true if the array can be split to two equals groups, that the amount of every group's numbers is equals to the other group. For exmaple, for this array:

int[]arr = {-3, 5, 12, 14, -9, 13};

The method will return true, since -3 + 5 + 14 = 12 + -9 + 13.

For this array:

int[]arr = {-3, 5, -12, 14, -9, 13};

The method will return false since even though -3 + 5 + 14 + -12 = -9 + 13, the amount of numbers in every side of the equation isn't equals.

For the array:

int[]arr = {-3, 5, -12, 14, -9};

The method will return false since array length isn't even.

The method must be recursive, overloading is allowed, every assist method must be recursive too, and I don't need to worry about complexity.

I've been trying to solve this for three hours, I don't even have a code to show since all the things I did was far from the solution.

If someone can at least give me some pseudo code it will be great.

Thank you very much!

Answer 1

You asked for pseudocode, but sometimes it's just as easy and clear to write it as Java.

The general idea of this solution is to try adding each number to either the left or the right of the equation. It keeps track of the count and sum on each side at each step in the recursion. More explanation in comments:

class Balance {
  public static void main(String[] args) {
    System.out.println(balanced(-3, 5, 12, 14, -9, 13));   // true
    System.out.println(balanced(-3, 5, -12, 14, -9, 13));  // false
  }

  private static boolean balanced(int... nums) {
    // First check if there are an even number of nums.
    return nums.length % 2 == 0
        // Now start the recursion:
        && balanced(
            0, 0,  // Zero numbers on the left, summing to zero.
            0, 0,  // Zero numbers on the right, summing to zero.
            nums);
  }

  private static boolean balanced(
      int leftCount, int leftSum,
      int rightCount, int rightSum,
      int[] nums) {
    int idx = leftCount + rightCount;
    if (idx == nums.length) {
      // We have attributed all numbers to either side of the equation.
      // Now check if there are an equal number and equal sum on the two sides.
      return leftCount == rightCount && leftSum == rightSum;
    } else {
      // We still have numbers to allocate to one side or the other.
      return
          // What if I were to place nums[idx] on the left of the equation?
          balanced(
              leftCount + 1, leftSum + nums[idx],
              rightCount, rightSum,
              nums)
          // What if I were to place nums[idx] on the right of the equation?
          || balanced(
              leftCount, leftSum,
              rightCount + 1, rightSum + nums[idx],
              nums);
    }
  }
}

This is just a first idea solution. It's O(2^n), which is obviously rather slow for large n, but it's fine for the size of problems you have given as examples.