更好地理解回溯的方法
Approaches to understand backtracking better
我想问一下是什么帮助你更好地掌握了回溯的概念。
我想我对它背后的想法和递归理解得足够好，但是，我很难理解为什么回溯会导致想要的结果。我试图将代码“干运行”在纸上，更好地理解程序流程，但几乎无济于事。
所以，自然地，我很难想出自己的回溯解决方案。
我想我明白为什么基本情况有意义，为什么 if 调用是必要的，并且看到每个选项都在检查（通过使用调试器），但我不明白为什么 java在内部以这种方式计算代码。
例如这里：https://codingbat.com/prob/p145416:
java
**
// 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
System.out.println("test"); // Why does it reach that point?
return false;
}
**
i wanted to ask what helped you grasp the concept of backtracking better.
为了掌握总体思路，它帮助我观看了使用回溯的解决方案的可视化（带有可视化的视频或页面）。
为了掌握调用和递归调用的工作原理，我只是通过调试做了很多步骤，还看了一些可视化。
从您添加到代码中的注释中，我可以看出您已经掌握了回溯的一般概念以及为什么存在这些条件和递归调用。
那么计算机（这不特定于 Java）如何执行调用和递归调用，更重要的是，它们如何跟踪调用完成后 return 的位置？
他们使用调用堆栈。来自维基百科
A call stack is used for several related purposes, but the main reason for having one is to keep track of the point to which each active subroutine should return control when it finishes executing. An active subroutine is one that has been called, but is yet to complete execution, after which control should be handed back to the point of call. Such activations of subroutines may be nested to any level (recursive as a special case), hence the stack structure.
调用堆栈通过每次调用发生时将堆栈帧压入（添加）堆栈并在活动调用 return 时弹出（移除）它们来跟踪仍在进行中的调用。
堆栈帧包含有关（简化）的信息：
- 调用的参数值
- return地址=代码中的位置return调用完成后
- 被调用方法的局部变量，context/scope
堆栈和堆栈帧使递归调用成为可能。
我知道您已经使用调试器在代码执行时单步执行，但让我们在“纸上”再做一次。
我将在您的代码中使用行号（我也删除了注释）以便于引用这些行。将递归调用的方法有5行代码。
boolean groupSum(int start, int[] nums, int target) {
1: if (start >= nums.length) return (target == 0);
2: if (groupSum(start + 1, nums, target - nums[start])) return true;
3: if (groupSum(start + 1, nums, target)) return true;
4: System.out.println("test"); // Why does it reach that point?
5: return false;
}
我们以调用groupSum(0, [2, 4, 8], 9)为例。
当您的代码的某些部分调用 groupSum(0, [2, 4, 8], 9) 时，它会将此调用推送到调用堆栈（创建堆栈帧）并开始执行方法体。
Stack frame 1 created: groupSum(0, [2, 4, 8], 9)
Parameters: start = 0, target = 9, nums = [2, 4, 8]
// Line 1 condition is false, so it keeps going
// Line 2 calls groupSum(0 + 1, [2, 4, 8], 9 - 2)
// which pushes a new stack frame on the call stack
Stack frame 2 created: groupSum(1, [2, 4, 8], 7)
Parameters: start = 1, target = 7, nums = [2, 4, 8]
// This creates a local scope (context) for frame 2.
// Frame 1 is isolated from changes to variables in Frame 2
// Line 1 condition is false, so it keeps going
// Line 2 calls groupSum(1 + 1, [2, 4, 8], 7 - 4)
// which pushes a new stack frame on the call stack
Stack frame 3 created: groupSum(2, [2, 4, 8], 3)
Parameters: start = 2, target = 3, nums = [2, 4, 8]
// Line 1 condition is false, so it keeps going
// Line 2 calls groupSum(2 + 1, [2, 4, 8], 3 - 8)
// which pushes a new stack frame on the call stack
Stack frame 4 created: groupSum(3, [2, 4, 8], -5)
Parameters: start = 3, target = -5, nums = [2, 4, 8]
// Line 1 condition is true. So the method returns (-5 == 0),
// which means it returns false.
这是第一次真正的回溯。它已到达数组的末尾，但尚未找到有效的解决方案，因为 -5 不为 0，因此它 returns 并返回调用堆栈 - 它回溯 .
一个 return 语句从调用堆栈中弹出一个帧，并在 return 地址继续执行代码 - 在代码中调用我们现在的方法的点 return来自.
在这种情况下，它弹出第 4 帧，恢复第 3 帧的局部作用域（恢复局部变量的所有值）并在第 2 行（第 3 帧）继续执行。 这使得回溯“有效”，因为它恢复了调用站点本地作用域的先前状态，然后从那里继续执行。
Stack frame 3 restored:
Parameters: start = 2, target = 3, nums = [2, 4, 8]
// Line 2 condition is false (because false was returned) so it keeps going
// Line 3 calls groupSum(2 + 1, [2, 4, 8], 3)
// which pushes a new stack frame on the call stack
Stack frame 4 created: // this is a completely new frame 4,
// has no relation to frame 4 from before
Parameters: start = 3, target = 3, nums = [2, 4, 8]
// Line 1 condition is true, it returns (3 == 0), so it returns false.
这里又回溯了这又从调用栈中弹出一个帧，所以第3帧的作用域恢复了，但是这次它继续在第3行执行
Stack frame 3 restored:
Parameters: start = 2, target = 3, nums = [2, 4, 8]
// Line 3 condition is false (because false was returned) so it keeps going
// Line 4 prints out "test". This is when and how this line is executed.
// Line 5 returns false.
这里也是回溯，因为两条调用路径（第2行和第3行的调用），都没有从当前状态找到解，都不得不回溯。
这会从调用堆栈中弹出一个帧，因此帧 2 的范围已恢复，它在第 2 行继续。
Stack frame 2 restored:
Parameters: start = 1, target = 7, nums = [2, 4, 8]
// Line 2 condition is false (because false was returned), so it keeps going
// Line 3 calls groupSum(1 + 1, [2, 4, 8], 7)
// which pushes a new stack frame on the call stack
创建堆栈帧 3 并重复整个过程，帧 4 的目标 7 - 8 = -1 和 7 的数字略有不同，但结果相同（错误 returned ，所以回溯）。
它在第 4 帧第 4 行再次打印“test”，并在第 5 行 returns false
然后第 3 行第 4 行打印“test”和 returns false 在第 5 行（回溯）并且第 2 帧在第 3 行再次恢复
Stack frame 2 restored:
Parameters: start = 1, target = 7, nums = [2, 4, 8]
// Line 3 condition is false (because false was returned) so it keeps going
// Line 4 prints "test"
// Line 5 returns false (backtracks)
Stack frame 1 restored:
Parameters: start = 0, target = 9, nums = [2, 4, 8]
// Line 2 condition is false, so it keeps going
// Line 3 repeats the whole thing with frames 2, 3 and 4,
// outcomes are still false (backtracks a few times),
// so after a few more "test" are printed, frame 1 is restored again,
// but this time on line 3 and since the returned value is false,
// the condition is false, so it keeps going
// Line 4 prints "test
// Line 5 returns false (backtracks)
此时，第 1 帧从调用堆栈中弹出，执行返回到方法的原始调用者 groupSum(0, [2, 4, 8], 9)，因此我们可以说“根帧”（第 0 帧）是恢复并且值 false 返回到原始呼叫者。
整个执行的结果是false，这是意料之中的，因为2, 4, 8中没有与9相加的组和。
编辑：这是另一个可能会派上用场的技巧（也许当你想出回溯算法时）。在 (Java) IDE 中，当调试器在断点处停止时，您还可以在调试器中看到当前调用堆栈的帧 window 以及当前作用域中变量的值。您还可以 select 其他框架并查看调用从何处开始以及该框架范围内的变量值。一些 IDE 甚至在代码中显示内联局部变量（如下图所示）。
这是来自 IDEA Community Edition 的示例
我想问一下是什么帮助你更好地掌握了回溯的概念。
我想我对它背后的想法和递归理解得足够好，但是，我很难理解为什么回溯会导致想要的结果。我试图将代码“干运行”在纸上，更好地理解程序流程，但几乎无济于事。
所以，自然地，我很难想出自己的回溯解决方案。
我想我明白为什么基本情况有意义，为什么 if 调用是必要的，并且看到每个选项都在检查（通过使用调试器），但我不明白为什么 java在内部以这种方式计算代码。
例如这里：https://codingbat.com/prob/p145416:
java
**
// 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
System.out.println("test"); // Why does it reach that point?
return false;
}
**
i wanted to ask what helped you grasp the concept of backtracking better.
为了掌握总体思路，它帮助我观看了使用回溯的解决方案的可视化（带有可视化的视频或页面）。 为了掌握调用和递归调用的工作原理，我只是通过调试做了很多步骤，还看了一些可视化。
从您添加到代码中的注释中，我可以看出您已经掌握了回溯的一般概念以及为什么存在这些条件和递归调用。
那么计算机（这不特定于 Java）如何执行调用和递归调用，更重要的是，它们如何跟踪调用完成后 return 的位置？
他们使用调用堆栈。来自维基百科
A call stack is used for several related purposes, but the main reason for having one is to keep track of the point to which each active subroutine should return control when it finishes executing. An active subroutine is one that has been called, but is yet to complete execution, after which control should be handed back to the point of call. Such activations of subroutines may be nested to any level (recursive as a special case), hence the stack structure.
调用堆栈通过每次调用发生时将堆栈帧压入（添加）堆栈并在活动调用 return 时弹出（移除）它们来跟踪仍在进行中的调用。
堆栈帧包含有关（简化）的信息：
- 调用的参数值
- return地址=代码中的位置return调用完成后
- 被调用方法的局部变量，context/scope
堆栈和堆栈帧使递归调用成为可能。
我知道您已经使用调试器在代码执行时单步执行，但让我们在“纸上”再做一次。
我将在您的代码中使用行号（我也删除了注释）以便于引用这些行。将递归调用的方法有5行代码。
boolean groupSum(int start, int[] nums, int target) {
1: if (start >= nums.length) return (target == 0);
2: if (groupSum(start + 1, nums, target - nums[start])) return true;
3: if (groupSum(start + 1, nums, target)) return true;
4: System.out.println("test"); // Why does it reach that point?
5: return false;
}
我们以调用groupSum(0, [2, 4, 8], 9)为例。
当您的代码的某些部分调用 groupSum(0, [2, 4, 8], 9) 时，它会将此调用推送到调用堆栈（创建堆栈帧）并开始执行方法体。
Stack frame 1 created: groupSum(0, [2, 4, 8], 9)
Parameters: start = 0, target = 9, nums = [2, 4, 8]
// Line 1 condition is false, so it keeps going
// Line 2 calls groupSum(0 + 1, [2, 4, 8], 9 - 2)
// which pushes a new stack frame on the call stack
Stack frame 2 created: groupSum(1, [2, 4, 8], 7)
Parameters: start = 1, target = 7, nums = [2, 4, 8]
// This creates a local scope (context) for frame 2.
// Frame 1 is isolated from changes to variables in Frame 2
// Line 1 condition is false, so it keeps going
// Line 2 calls groupSum(1 + 1, [2, 4, 8], 7 - 4)
// which pushes a new stack frame on the call stack
Stack frame 3 created: groupSum(2, [2, 4, 8], 3)
Parameters: start = 2, target = 3, nums = [2, 4, 8]
// Line 1 condition is false, so it keeps going
// Line 2 calls groupSum(2 + 1, [2, 4, 8], 3 - 8)
// which pushes a new stack frame on the call stack
Stack frame 4 created: groupSum(3, [2, 4, 8], -5)
Parameters: start = 3, target = -5, nums = [2, 4, 8]
// Line 1 condition is true. So the method returns (-5 == 0),
// which means it returns false.
这是第一次真正的回溯。它已到达数组的末尾，但尚未找到有效的解决方案，因为 -5 不为 0，因此它 returns 并返回调用堆栈 - 它回溯 .
一个 return 语句从调用堆栈中弹出一个帧，并在 return 地址继续执行代码 - 在代码中调用我们现在的方法的点 return来自.
在这种情况下，它弹出第 4 帧，恢复第 3 帧的局部作用域（恢复局部变量的所有值）并在第 2 行（第 3 帧）继续执行。 这使得回溯“有效”，因为它恢复了调用站点本地作用域的先前状态，然后从那里继续执行。
Stack frame 3 restored:
Parameters: start = 2, target = 3, nums = [2, 4, 8]
// Line 2 condition is false (because false was returned) so it keeps going
// Line 3 calls groupSum(2 + 1, [2, 4, 8], 3)
// which pushes a new stack frame on the call stack
Stack frame 4 created: // this is a completely new frame 4,
// has no relation to frame 4 from before
Parameters: start = 3, target = 3, nums = [2, 4, 8]
// Line 1 condition is true, it returns (3 == 0), so it returns false.
这里又回溯了这又从调用栈中弹出一个帧，所以第3帧的作用域恢复了，但是这次它继续在第3行执行
Stack frame 3 restored:
Parameters: start = 2, target = 3, nums = [2, 4, 8]
// Line 3 condition is false (because false was returned) so it keeps going
// Line 4 prints out "test". This is when and how this line is executed.
// Line 5 returns false.
这里也是回溯，因为两条调用路径（第2行和第3行的调用），都没有从当前状态找到解，都不得不回溯。
这会从调用堆栈中弹出一个帧，因此帧 2 的范围已恢复，它在第 2 行继续。
Stack frame 2 restored:
Parameters: start = 1, target = 7, nums = [2, 4, 8]
// Line 2 condition is false (because false was returned), so it keeps going
// Line 3 calls groupSum(1 + 1, [2, 4, 8], 7)
// which pushes a new stack frame on the call stack
创建堆栈帧 3 并重复整个过程，帧 4 的目标 7 - 8 = -1 和 7 的数字略有不同，但结果相同（错误 returned ，所以回溯）。
它在第 4 帧第 4 行再次打印“test”，并在第 5 行 returns false
然后第 3 行第 4 行打印“test”和 returns false 在第 5 行（回溯）并且第 2 帧在第 3 行再次恢复
Stack frame 2 restored:
Parameters: start = 1, target = 7, nums = [2, 4, 8]
// Line 3 condition is false (because false was returned) so it keeps going
// Line 4 prints "test"
// Line 5 returns false (backtracks)
Stack frame 1 restored:
Parameters: start = 0, target = 9, nums = [2, 4, 8]
// Line 2 condition is false, so it keeps going
// Line 3 repeats the whole thing with frames 2, 3 and 4,
// outcomes are still false (backtracks a few times),
// so after a few more "test" are printed, frame 1 is restored again,
// but this time on line 3 and since the returned value is false,
// the condition is false, so it keeps going
// Line 4 prints "test
// Line 5 returns false (backtracks)
此时，第 1 帧从调用堆栈中弹出，执行返回到方法的原始调用者 groupSum(0, [2, 4, 8], 9)，因此我们可以说“根帧”（第 0 帧）是恢复并且值 false 返回到原始呼叫者。
整个执行的结果是false，这是意料之中的，因为2, 4, 8中没有与9相加的组和。
编辑：这是另一个可能会派上用场的技巧（也许当你想出回溯算法时）。在 (Java) IDE 中，当调试器在断点处停止时，您还可以在调试器中看到当前调用堆栈的帧 window 以及当前作用域中变量的值。您还可以 select 其他框架并查看调用从何处开始以及该框架范围内的变量值。一些 IDE 甚至在代码中显示内联局部变量（如下图所示）。
这是来自 IDEA Community Edition 的示例