java - 追踪递归

Question

我正在学习递归，但在跟踪递归方面遇到了困难。 这是我的问题，我有一个工作得很好的解决方案。 我被困在某个时刻，无法继续跟踪。

问题: 给定一个整数数组，是否可以选择一组某些整数，使得该组的总和等于给定的目标。

解决方案:

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

start = 0(我们必须在此处启动数组)

nums[]={10,8,6} 目标 = 16

请帮我追踪问题？

Answer 1

首先对行进行编号

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

这是执行(假设这就是您所要求的):

1 call groupSum1(0, {10, 8, 6}, 16)
    1. 0 < 3 next
2 call groupSum1(1, {10, 8, 6}, 6)
    1. 1 < 3 next
3 call groupSum1(2, {10, 8, 6}, -2)
    1. 2 < 3 next
4 call groupSum1(3, {10, 8, 6}, -8)
    1. 3 == 3 return false to call 3      
back to call 3 in line 2.
5 call groupSum1(3, {10, 8, 6}, -2)
    1. 3 == 3 return false to call 3
back to call 3 in line 3.
    return false to call 2
back to call 2 in line 2.
6 call groupSum1(2, {10, 8, 6}, 6)
    2 < 3 next
7 call groupSum1(3, {10, 8, 6}, 0)
    3 == 3 return true to call 6
back to call 6 in line 2.
    return true to call 2
back to call 2 in line 3.
    return true to call 1
back to call 1 in line 2.
    return true

递归调用前面的数字只是我用来跟踪深度的索引。我希望这是可以理解的。