包含 5 的倍数的布尔递归

Question

这是我正在处理的问题： “给定一个整数数组，是否可以选择一组一些整数，使得该组总和达到给定的目标，并具有这些额外的约束：数组中所有 5 的倍数都必须包含在该组中。如果紧跟在 5 的倍数后面的值是 1，不能选择它。（不需要循环。）"

我尝试了以下方法：

public boolean groupSum5(int start, int[] nums, int target) {
  if (start == nums.length) return (target == 0);
  if (groupSum5(start + 1, nums, target - nums[start]) && nums[start] % 5 == 0)
    return true;
  if (groupSum5(start + 1, nums, target)) return true;
  return false;
}

但它只能得到5的倍数，我试过这个：

public boolean groupSum5(int start, int[] nums, int target) {
  if (start == nums.length) return (target == 0);
  if (groupSum5(start + 1, nums, target - nums[start]) && nums[start] % 5 == 0)
    return true;
  if (groupSum(start + 1, nums, target - nums[start])) return true;
  if (groupSum5(start + 1, nums, target)) return true;
  return false;
}

但这不起作用，因为有时不包括 5 的倍数。

我知道我的代码还没有满足第二个约束条件。

有什么想法吗？

编辑：

Answer 1

if (groupSum5(start + 1, nums, target - nums[start]))

对于您输入的每个数字，您需要选择是否包括它，或者不包括它。 if 是 'include it' 选项：这就是为什么要将目标值减少的原因。

&& nums[start] % 5 == 0

...所以这意味着：不可能包含任何给定值，除非它是 5 的倍数。这不是问题描述要你做的!

问题描述要你做的是：如果你所在的数字是 5 的倍数，那么它必须包括在内。您不能选择不包含它。

因此，您在错误的 if 和错误的方式上施加了约束。你真正想要的是第二个if，它涵盖了要修改的'lets not pick this number'：

if (!num[start] % 5 == 0 && groupSum5(start, nums, target)) return true;

换句话说：如果我们使用的数字不是 5 的倍数，那么尝试不包括这个数字，看看是否可行。（因为当它是 5 的倍数时试图不包括它是无效的）。

If the value immediately following a multiple of 5 is 1, it must not be chosen.

那是另一个约束，这个约束必须应用于第一个 if（代表 'lets include this number' 的那个）。如果需要一些额外的 && 来过滤 -OUT- 你所在的数字是 1 的情况，AND 它不是序列中的第一个数字，AND 序列中的前一个数字是 5 的倍数：在这种情况下，'include the number' 不是有效着法。

使用反转条件（前面有一个!）和&&，类似于上面的例子。您想要完成的是，如果 'try including this number and then see if we can work it out by applying this algorithm to the remainder of the list' 的步骤由于附加约束而无效，则该步骤将被简单地跳过。

包含 5 的倍数的布尔递归

Boolean Recursion with multiples of 5 included

java

recursion

boolean