2

我遇到了提高我的编码技能的递归练习，并发现了以下问题。

给定一个整数数组，是否可以选择一组整数，使得该组总和为给定目标？我们的惯例不是查看整个数组，而是考虑从索引开始到数组末尾的数组部分。调用者可以简单地通过将 start 传递为 0 来指定整个数组。不需要循环——递归调用沿着数组向下进行。

groupSum(0, [2, 4, 8], 10) → true
groupSum(0, [2, 4, 8], 14) → true
groupSum(0, [2, 4, 8], 9) → false

经过2天的工作和学习，我什么都没有。我检查了给定的解决方案，但在逐步调试后我仍然无法理解解决方案。

public boolean groupSum(int start, int[] nums, int target) {
  // Base case: if there are no numbers left, then there is a
  // solution only if target is 0.
  if (start >= nums.length) return (target == 0);

  // Key idea: nums[start] is chosen or it is not.
  // Deal with nums[start], letting recursion
  // deal with all the rest of the array.

  // Recursive call trying the case that nums[start] is chosen --
  // subtract it from target in the call.
  if (groupSum(start + 1, nums, target - nums[start])) return true;

  // Recursive call trying the case that nums[start] is not chosen.
  if (groupSum(start + 1, nums, target)) return true;

  // If neither of the above worked, it's not possible.
  return false;
}

解决方案很短，其逻辑是基于组合的。你怎么看待这件事？它背后的算法解释是什么？

问候

4

3 回答 3

4

这只是基本的回溯：

if (start >= nums.length) return (target == 0);

- 这里我们过去了所有的输入，当剩余的要填充的目标是 0 时我们就成功了

if (groupSum(start + 1, nums, target - nums[start])) return true;

- 在这里，我们尝试使用 position 处的元素填充目标start：

  • 转移开始到下一个位置
  • 从目标中减去当前元素（这等于包括所选集合中的当前元素）
if (groupSum(start + 1, nums, target)) return true;

- 在这里，我们正在尝试相同的操作，但不使用 position 的元素start

从最后一个元素读取：

  • 如果没有更多元素，如果 target 为 0，我们就成功了
  • 否则，如果我们可以使用或不使用当前元素将剩余元素与目标匹配，我们就会成功
于 2016-12-12T14:25:06.520 回答
3

所以假设你的问题是：

  • 你能用数字 [2, 3, 5, 8] 创建 9 的总和吗？

如果以下至少一个问题为真，则此问题为真：

  • 你能用数字 [3, 5, 8] 创建 9 的总和吗？
  • 你能用数字 [3, 5, 8] 创建一个 7 的总和吗？

因此，您用两个关于 3 元素列表的新问题替换了最初关于 4 元素列表的问题。

当您再这样做 3 次时，您最终会遇到 16 个关于 0-element-lists 的问题。如果至少其中一个的目标为零，那么您最初问题的答案是肯定的。

于 2016-12-12T14:28:31.663 回答
0

它基于动态规划。基本上，您将一个问题分解为许多更易于解决的子问题。

以下是对此特定问题的一些解释：单击。

于 2016-12-12T14:24:22.577 回答