Java递归问题

Question

我在Java中有一个递归面试的问题，需要你的帮助。

编写这样的**Java function** :：给定一个整数数组，是否可以将这两个整数分成两组，使得两组的总和相同，并且具有以下约束:所有是5的倍数的值必须在一个组中，所有是3的倍数(而不是5的倍数)的值必须在另一个组中。(不需要循环。)

split53({1,1}) → true

split53({1, 1, 1}) → false

split53({2, 4, 2}) → true

PS:这是惠普的面试问题

Answer 1

这个问题可以很容易地归结为:给定一组整数numbers和一个整数target，是否有可能找到numbers的一个子集，其sum等于target

如果过渡需要澄清，请让我知道。

它可以在O(numbers.size * target)时间内用DP来解决。我的想法如下

当numbers.size为0时，唯一可达的和是我们有numbers == {1, 3}，在这种情况下{0, 1, 3, 4}是可用的。如果我们向numbers添加另一个元素4会怎么样？现在，所有的旧和仍然可以达到，也可以达到一些新的和：{0 + 4, 1 + 4, 3 + 4, 4 + 4}。因此，对于numbers == {1, 3, 4}，可用金额是这种方式，将数字逐个相加，您可以构建可达金额的列表。

一个工作示例(它不处理负数，但您可以很容易地修复它)

boolean splittable(int[] numbers, int target) {
    boolean[] reached = new boolean[target + 1];
    reached[0] = true;

    for (int number : numbers) {
        for (int sum = target - 1; sum >= 0; --sum) {
            if (reached[sum] && sum + number <= target) {
                reached[sum + number] = true;
            }
        }
    }

    return reached[target];
}

运行它

System.out.println(splittable(new int[]{3, 1, 4}, 7)); // => true
System.out.println(splittable(new int[]{3, 1, 4}, 6)); // => false

编辑

我只是注意到了需求中的“递归”部分。好吧，DP可以用memoization重写为递归，如果这是一个很难的要求。这将保持运行时的复杂性。

编辑2个

在组上。在继续执行算法之前，必须将可被3或5整除的元素分配给各自的组。假设所有元素的和是s，可被3整除的元素和是s3，但不能被3整除的元素和是s5。在这种情况下，在分配了这些“特殊”元素后，您必须将剩余的和分成两组，一组为s/2 - s3，另一组为s/2 - s5。

Answer 2

非常慢，但有效的解决方案：

static boolean canSplit(int[] arr, int lvl, int sum1, int sum2) {
        if (arr.length == lvl) {
            if (sum1 == sum2) {
                return true;
            } else {
                return false;
            }
        }
        if (arr[lvl] % 5 == 0) {
            return canSplit(arr, lvl + 1, sum1 + arr[lvl], sum2);
        } else if (arr[lvl] % 3 == 0) {
            return canSplit(arr, lvl + 1, sum1, sum2 + arr[lvl]);
        }
        return canSplit(arr, lvl + 1, sum1 + arr[lvl], sum2) ||
               canSplit(arr, lvl + 1, sum1, sum2 + arr[lvl]);
    }

调用函数：

canSplit(arr, 0, 0, 0);

Answer 3

这是真正的递归解决方案。

private boolean split2(int index, int[] nums, int sum1, int sum2) {
  if (index >= nums.length) {
    return sum1 == sum2;
  }

  if (split2(index + 1, nums, sum1 + nums[index], sum2)) {
    return true;
  }
  if (split2(index + 1, nums, sum1, sum2 + nums[index])) {
    return true;
  }

  return false; 
}

这段代码将每个元素放入其中一个组中。如果两个组的任意组合相等，则返回true。没有使用循环，并且只在一个函数中。

对所有人都最好

编辑:您的函数接受4个参数作为输入，而问题只接受数组作为输入。您必须指定所需的函数可以通过调用split2(0,nums,0,0);使用您的函数来完成