java - CodingBat split53；对使用返回的正确方法感到困惑

Question

我有点困惑为什么我的下面的解决方案没有给出正确的答案。我做了一些挖掘，我猜这与调用的工作方式有关？我认为这两种方式是相同的，但事实并非如此，但我不完全理解我的错误返回的是什么。这是我之前做的研究:https://softwareengineering.stackexchange.com/questions/333247/why-does-recursion-return-the-first-call-in-the-stack-and-not-the-last

问题:

给定一个整数数组，是否可以将整数分为两组，使两组的总和相同，但有以下约束:所有是 5 的倍数的值必须在一组中，所有是 3 的倍数(而不是 5 的倍数)的值必须在另一组中。 (不需要循环。)

示例:

split53([1, 1]) → true

split53([1, 1, 1]) → 假

split53([2, 4, 2]) → true

我的回答:

public boolean split53Helper(int start, int [] nums, int group3, int group5){
  if(start >= nums.length){
    return group3 == group5;
  }

  if(nums[start] % 3 == 0 ){
    if (split53Helper(start + 1, nums, group3 + nums[start], group5)){
      return true;
    }
  }

  if(nums[start] % 5 == 0){
    if (split53Helper(start + 1, nums, group3, group5 + nums[start])){
      return true;
    }
  }

  if(split53Helper(start+1, nums, group3 + nums[start], group5))
      return true;

  if(split53Helper(start+1, nums, group3, group5 + nums[start]))
      return true;

  return false;
}

正确的解决方案:

public boolean split53(int[] nums) {
    return split53Helper(0, nums, 0, 0);
}

public boolean split53Helper(int start, int[] nums, int mult5, int mult3) {
    if(start >= nums.length)
        return mult5 == mult3;

    if(nums[start] % 5 == 0)
        return split53Helper(start+1, nums, mult5 + nums[start], mult3);

    if(nums[start] % 3 == 0)
        return split53Helper(start+1, nums, mult5, mult3 + nums[start]);

    if(split53Helper(start+1, nums, mult5 + nums[start], mult3))
        return true;

    if(split53Helper(start+1, nums, mult5, mult3 + nums[start]))
        return true;

    return false;
}

我的代码没有返回最后一次调用吗？如果是这样，我什么时候会使用一种返回方法而不是另一种方法？如果已经有完整的解释，请告诉我。我以为我理解堆栈和函数调用是如何工作的，但现在我担心我正朝着错误的方向前进。

Answer 1

这是正确的解决方案，经过重写以看起来更类似于您的答案:

public boolean split53Helper(int start, int [] nums, int group3, int group5){
  if(start >= nums.length){
    return group3 == group5;
  }

  if(nums[start] % 3 == 0 ){
    if (split53Helper(start + 1, nums, group3 + nums[start], group5)){
      return true;
    } else {
      return false; // <-------
    }
  }

  if(nums[start] % 5 == 0){
    if (split53Helper(start + 1, nums, group3, group5 + nums[start])){
      return true;
    } else {
      return false; // <-------
    }
  }

  if(split53Helper(start+1, nums, group3 + nums[start], group5))
      return true;

  if(split53Helper(start+1, nums, group3, group5 + nums[start]))
      return true;

  return false;
}

现在您应该看到您的答案与正确的解决方案有何不同。如果第一个递归调用返回 false，您的答案将继续调用第三个和第四个递归调用，而正确的解决方案不会。

当递归方法处理数组时，它几乎总是遵循“对一个元素执行某些操作，然后(递归地)对其余元素执行此操作”模式。递归调用询问“能否将数组的其余部分分为 2 组，总和为相同的数字......？”。

当一个元素可以被 3 整除时，你把它放在 3 的组中并问同样的问题，因此调用:

split53Helper(start + 1, nums, group3 + nums[start], group5)

如果这个问题的答案是“否”，那么您就不应该问“如果我把它放在 5 组中怎么办？” (我指的是您答案中的第四次递归调用)

split53Helper(start + 1, nums, group3, group5 + nums[start])

不能将其放入 5 组中，因为已知该元素可被 3 整除。

这就是为什么当你知道它能被 3 整除时你应该立即返回，而其余的不能被分成组。