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

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?» (Я имею в виду 4-й рекурсивный вызов в вашем ответе)

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

Нельзя поместить его в группу 5, поскольку известно, что элемент делится на 3.

Вот почему вы должны немедленно вернуться, когда узнаете, что оно делится на 3, а остальные нельзя разделить на группы.

Answer 2

Ниже приведено объяснение правильного решения.
Я думаю, что решение заключается в сканировании чисел, хранящихся в числах, и проверке, делится ли оно на 3 или 5 или нет.

В случае, если он делится на 3, вы добавляете его в группу 3 и переходите к следующему номеру.
В случае, если он делится на 5, вы добавляете его в группу 5 и переходите к следующему числу.
В случае, если он не делится ни на один, вы попробуйте добавить к обоим и перейти к следующему номеру. После того как вы отсканировали все числа, вы проверяете, равно ли group3 группе 5

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