如何编写一个递归布尔函数来查找数组是否可以从i到长度-1拆分为两个段和，使其等于diff

Question

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

没有循环或辅助方法，我需要检查arr[i...arr.length-1]是否有一个等于diff的两段和，例如我有：diff=1， i=2， arr={3, 4, 1, 1, 2, 0, 1, 1, 3}它返回true，因为总和{1,1,2,0}（4）减去总和{1,1,3}（5）等于diff（1）。我试图想办法甚至没有循环的总和arr，我唯一想到的是将其添加到diff，但后来我失去了我原来的diff加上我不知道元素的数量，所以我可以在我的返回语句中添加“或”，所以现在我出主意了。

Answer 1

我假设您的限制是没有循环和库使用。您可能需要一些附加功能。此外，我假设差分检查应使用绝对值，即第一个和或第二个和是否较小无关紧要，只要差分匹配（-1或1）。话虽如此，第一种方法可能是这样的：

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]);
  }
}

关键是系统地将数组分为两部分，从一开始就检查每个部分的总和与差值。然后进一步剪切一个索引，如果不匹配，则重复该过程。最后，如果没有其他元素，则必须以false退出。边缘有点粗糙。请随时改进它并修复可能存在的错误。打印语句用于调试目的。当然，人们可能会争论JUnit和java。util。数组是库函数。如果需要的话，可以用一点额外的努力来代替这些。