艰难的递归任务

Question

作为考试准备的一部分，我一直在努力解决问题，我想我需要你的帮助。我需要写一个布尔方法，需要整数数组（正和负），并返回true，如果数组可以被拆分为两个相等的组，每个组的数字的量等于另一组。对于示例，对于这个数组：

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

该方法将返回true，因为-3514=12-913。

对于此阵列：

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

该方法将返回false，因为即使-3 5 14 -12 = -9 13，等式每边的数字量也不相等。

对于阵列：

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

该方法将返回false，因为数组长度不是偶数。

方法必须是递归的，允许重载，每个辅助方法也必须是递归的，我不需要担心复杂性。

我已经试着解决这个问题三个小时了，我甚至没有代码可以显示，因为我所做的一切都离解决方案相去甚远。

如果有人至少能给我一些伪代码，那就太好了。

非常感谢你！

Answer 1

你的策略应该是尝试所有可能的组合。我将试图记录我将如何到达这一步。

请注意，我认为要求：让每个函数都使用递归有点难，因为我会通过省略一些帮助函数来解决这个问题，这些帮助函数使代码更具可读性，所以在这种情况下，我不会这样做。

使用递归，您总是希望向最终解决方案前进，并在完成时进行检测。因此，我们的功能需要两个部分：

1. 递归步骤：我们将获取输入集的第一个元素，并尝试将其添加到第一个集合中会发生什么，如果没有找到解决方案，我们将尝试将其添加到第二个集合中会发生什么。
2. 检测我们什么时候完成，也就是输入集是空的时候，在这种情况下，我们要么找到了解决方案，要么没有。

我们第一步的一个技巧是，在获取集合的第一个元素后，如果我们试图划分余数，我们不希望这两个集合不再相等，因为我们已经将第一个元素分配给其中一个集合。

这导致了一个遵循此策略的解决方案：

public boolean isValidSet(MySet<int> inputSet, int sizeDifferenceSet1minus2)
{
    if (inputSet.isEmpty())
    {
         return sizeDifferenceSet1minus2== 0;
    }

    int first = inptuSet.takeFirst();
    return isValidSet(inputSet.copyMinusFirst(), sizeDifferenceSet1minus2+ first)
              || isValidSet(inputSet.copyMinusFirst(), sizeDifferenceSet1minus2+ -1 * first);
}

这段代码需要一些您仍然需要实现的帮助函数。

它所做的是首先测试我们是否达到了结束条件，如果达到了，则返回这个分区是否成功。如果集合中仍然有元素，我们尝试将其添加到第一个集合中会发生什么，然后将其添加到第二个集合中会发生什么。请注意，我们实际上并不跟踪集合，我们只是跟踪集合1减去2之间的大小差异，减少（但相反，您可以沿着两个集合传递）。

还要注意，要使此实现正常工作，您需要复制输入集，而不是修改它！

对于一些背景信息：这个问题被称为分区问题，它以NP完全而闻名（这意味着可能不可能对大量输入数据有效地解决它，但很容易验证分区确实是一个解决方案）。

Answer 2

所描述的问题是分区问题的一个版本。首先注意，你的公式相当于决定输入是否有一个子集，它求和到所有元素总和的一半（需要是整数，否则实例无法求解，但这很容易检查）。基本上，在每个递归步骤中，要决定是否将第一个数字选入子集，从而产生不同的递归调用。如果n表示元素的数量，则必须选择n/2（需要再次积分）项。

让Sum表示输入的总和，让Target：=Sum/2在续集中被假定为整数

f(arr,a,count) := true
                  if there is a subset of arr summing up to a with
                  exactly count elements
                  false
                  otherwise

我们得到以下递归

f(arr,a,count) = (arr[0] == a && count == 1)
                 ||
                 (a == 0 && count == 0)
                 if arr contains only one element
                 f(arr\arr[0], a, count)
                 ||
                 f(arr\arr[0], a - arr[0], count -1)
                 if arr contains more than one element

其中||表示逻辑拒绝，

最后，f（arr，Target，n/2）生成所需的值。

Answer 3

您要求伪代码，但有时编写它和Java一样简单明了。

此解决方案的总体思路是尝试将每个数字添加到等式的左侧或右侧。它在递归的每一步跟踪每边的计数和总和。评论中有更多解释：

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

这只是第一个解决方案。它是O（2^n），对于大的n，这显然是相当慢的，但是对于您作为示例给出的问题的大小来说，这是很好的。