CodingBat split53;对正确的使用方法感到困惑 returns

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]) → 真

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

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

我的回答：

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

请在下面找到正确解决方案的解释。
我认为，解决方案是扫描存储在 nums 中的数字，并检查它是否可以被 3 或 5 或其中的 none 整除。

如果它能被 3 整除，您将它添加到 group3 并继续下一个数字。
如果它可以被 5 整除，则将其添加到 group5 并继续下一个数字。
如果它不能被 none 整除，您尝试将两者相加并继续下一个数字扫描完所有数字后，检查 group3 是否等于 group5

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

      if(nums[start] % 3 == 0 ){
         /**
          * In this case you dont have any choice as the number is divisble by 3.
          * You should add the number to group3 and move on with next number.
          * Dont put the below statement in if condition
          */
        return split53Helper(start + 1, nums, group3 + nums[start], group5);
      }

      if(nums[start] % 5 == 0){
        /**
          * In this case you dont have any choice as the number is divisble by 5.
          * You should add the number to group5 and move on with next number.
          * Dont put the below statement in if condition
          */
        return split53Helper(start + 1, nums, group3, group5 + nums[start]);
      }

      // Here you have choice, you can either put the number in group3 or group5

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

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

      return false;
    }

Answer 2

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

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

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

当递归方法处理数组时，它几乎总是遵循这种 "do something to one element, and then (recursively) do it to the rest of the elements" 模式。递归调用要求 "can the rest of the array be divided into 2 groups that sums to the same number...?".

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

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

如果这个问题的答案是"no"，你不应该再问"well what if I put it in the 5's group?"（我指的是你答案中的第4次递归调用）

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

你不能把它放在 5 的组中，因为已知该元素可以被 3 整除。

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

CodingBat split53;对正确的使用方法感到困惑 returns

CodingBat split53; Confused about the right way to use returns

java

recursion

function-call