public static boolean isSplitable(int[] arr, int diff, int i)

no loops or helper methods i need to check if arr[i...arr.length - 1] has a two section sum that is equal to diff for example i have: diff = 1, i = 2, arr = {3, 4, 1, 1, 2, 0, 1, 1, 3} it returns true because sum of {1, 1, 2, 0}(4) minus the sum of {1, 1, 3}(5) equals diff(1). i have tried to think of ways to even sum arr without a loop only thing i came up with is adding it to diff but then i lose my original diff plus i dont know the amount of elements so i can add "or" in my return statement so now im out of ideas.

CodePudding user response：

I'm assuming your restrictions are no loops and no library usage. You probably need some kind of additional functions. Moreover, I assume the difference check shall use absolute values, i.e. it does not matter if the first or second sum is smaller, as long as the difference matches (-1 or 1 in your example). That being said, a first approach could look like this:

import org.junit.jupiter.api.Test;

import static java.util.Arrays.copyOfRange;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;

public class RecursiveSplitTest {

  @Test
  public void testIsSplitable() {
    {
      int[] array = {3, 4, 1, 1, 2, 0, 1, 1, 3};
      assertTrue(isSplitable(array, 1, 2));
    }
    {
      int[] array = {3, 4, 1, 1, 1, 0, 4, 1, 3};
      assertTrue(isSplitable(array, 1, 4));
    }
    {
      int[] array = {3, 4, 1, 1, 1, 0, 4, 1, 3};
      assertFalse(isSplitable(array, 1, 7));
    }
    {
      int[] array = {3};
      assertFalse(isSplitable(array, 1, 1));
    }
  }

  public static boolean isSplitable(int[] array, int diff, int start) {
    if (start < 0 || start > array.length - 2) {
      System.out.println("Not possible due to initial parameters");
      return false;
    }

    return doSplitableRecursive(copyOfRange(array, start, array.length), diff, 0);
  }

  private static boolean doSplitableRecursive(int[] array, int diff, int start) {
    if (start   1 >= array.length) {
      System.out.println("Could not find it");
      return false;
    }

    int[] left = copyOfRange(array, 0, start   1);
    int[] right = copyOfRange(array, start   1, array.length);

    int leftSum = sum(left, 0);
    int rightSum = sum(right, 0);
    System.out.println("leftSum: "   leftSum);
    System.out.println("rightSum: "   rightSum);

    if (leftSum   diff == rightSum || leftSum - diff == rightSum) {
      System.out.println("Found match for cut at start   "   (start   1));
      return true;
    }

    return doSplitableRecursive(array, diff, start   1);
  }

  private static int sum(int[] array, int current) {
    if (array.length == 0) {
      return current;
    }

    return sum(copyOfRange(array, 1, array.length), current   array[0]);
  }
}

The key is to systematically divide the array in two pieces, beginning at start and checking the sum of each piece against the difference. Then cutting one index further and repeating the process if it did not match. Finally, you have to exit with false if there are no more elements left. It is a little rough around the edges. Feel free to improve it and fix possibly remaining bugs. The print statements are for debugging purposes. Of course, one could argue JUnit and java.util.Arrays are library functions. These can be replaced with a little bit of extra effort if needed.