1

以下问题来自codingbat：给定一个整数数组，是否可以选择一组整数，使得该组总和为给定目标？

该网站的作者提供了以下解决方案：

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

假设我想尝试以下情况，其中 nums=[2,4,8] 并调用 groupSum(0,nums,10)。

我看到那groupSum(0,nums,10)会调用groupSum(1,nums,10)and groupSum(1,nums,8)。

groupSum(1,nums,10)通话groupSum(2, nums,10)和groupSum(2, nums,6)

groupSum(1,nums,8)通话groupSum(2,nums,8)和groupSum(1,nums,4)

ETC...

通过代码工作，我看到以下调用：

groupSum(3,nums,10)
groupSum(3,nums,2)
groupSum(3,nums,6)
groupSum(3,nums,-2)
groupSum(3,nums,8)
groupSum(3,nums,0)
groupSum(3,nums,4)
groupSum(3,nums,-4)

groupSum(3,nums,0)由于第一行，我看到应该返回 true：
if (start >= nums.length) return (target == 0);但是我对其他调用感到困惑，例如groupSum(3,nums,-4). 从第一行开始，它应该清楚地导致 false since target != 0。

也有人可以解释为什么 return true 声明是必要的

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

我认为第一行将确定真假。

if (groupSum(start + 1, nums, target)) return true;
4

2 回答 2

7

基本上该功能可以分解为：

  1. 如果“开始”（数字数组中的当前位置）是数组末尾的一部分（换句话说，如果我们已经尝试了所有数字），那么如果达到目标（即是零）

  2. 否则，继续迭代 ( start+1) 并包含当前数字 ( target-nums[start])，如果可行则返回true

  3. 否则，包括当前编号不起作用，因此继续迭代而不使用当前编号。如果可行，请返回true

  4. 如果我们已经到了这一点，那么就没有办法添加有效的数字，所以 return false。

您已经分解了所有可能的函数调用的步骤，并且正如您所观察到的，有一个返回 true（目标为零的那个）。此true结果级联备份递归作为最终返回值。

以下是其工作原理的粗略细分：

groupSum(0,[2,4,8],10)
0 >= 3? no, so continue:
groupSum(1,[2,4,8],10-2)?
  1 >= 3? no, so continue:
  groupSum(2,[2,4,8],8-4)?
    2 >= 3? no, so continue:
    groupSum(3,[2,4,8],4-8)?
      3 >= 3? yes. -4 == 0? no, return false
    groupSum(3,[2,4,8],4)?
      3 >= 3? yes. 4 == 0? no, return false
    return false
  groupSum(2,[2,4,8],8)?
    2 >= 3? no, so continue:
    groupSum(3,[2,4,8],8-8)?
      3 >= 3? yes. 0 == 0? yes, return true
    yes, return true
  yes, return true
yes, return true

希望这可以帮助！

于 2013-08-03T04:39:08.413 回答
2

除了 Kolink 的详细演练，对于它的价值，在 Java 中，我创建了这个来帮助我了解：

public class TestRecursion{

    public static boolean groupSum(int start, int[] nums, int target, String s) {
        System.out.println(new String(new char[start]).replace("\0", "    ")+"start="+start+" target="+target+" parent="+s);
        if (start >= nums.length) return (target == 0);
        if (groupSum(start + 1, nums, target - nums[start], "A:"+start+"_"+target)) return true;
        if (groupSum(start + 1, nums, target, "B:"+start+"_"+target)) return true;
        return false;
    }

    public static void main(String... args){
        int[] nums = {2,4,8};
        groupSum(0, nums, 10, "");
    }
}

输出：

start=0 target=10 parent=
    start=1 target=8 parent=A:0_10
        start=2 target=4 parent=A:1_8
            start=3 target=-4 parent=A:2_4
            start=3 target=4 parent=B:2_4
        start=2 target=8 parent=B:1_8
            start=3 target=0 parent=A:2_8
于 2013-08-03T05:05:45.717 回答