包含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

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

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

&nums[start]%5==0

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

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

因此，您将约束加在错误的if上，并且是错误的。您实际上想要的是第二个if,它包含了要修改的“letnot pick this number”：

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

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

如果紧接在5的倍数后面的值为1，则不得选择该值。

这是另一个约束，这个约束必须应用于第一个if（表示'lets include this number')。如果需要一些额外的&来过滤--如果您所在的数字是1，并且它不是序列中的第一个数字，并且序列中的前一个数字是5的倍数：在这种情况下，“包含该数字”不是有效的移动。

使用反向条件（前面有一个！)和&&，类似于上面的示例。您想要完成的是，如果由于附加的约束而导致该步骤无效，那么“尝试包含这个数字，然后看看我们是否可以通过将该算法应用到列表的剩余部分来计算它”的步骤将被简单地跳过。