为什么回溯有时我们需要在递归后显式弹出，有时我们不需要？

Question

例如，让我们考虑一个任务，我们需要找到给定字符串的所有排列，保留字符序列但改变大小写。

这里是没有.pop()的回溯解决方案：

def letterCasePermutation(S):
    """
    :type S: str
    :rtype: List[str]
    """
    def backtrack(sub="", i=0):
        if len(sub) == len(S):
            res.append(sub)
        else:
            if S[i].isalpha():
                backtrack(sub + S[i].swapcase(), i + 1)
            backtrack(sub + S[i], i + 1)
            
    res = []
    backtrack()
    return res

这是 .pop() 的解决方案：

def letterCasePermutation(s):
    def backtrack(idx, path):
        if idx == n:
            res.append("".join(path))
            return
        
        ele = s[idx]
        if ele.isnumeric():
            path.append(ele)
            backtrack(idx + 1, path)
            path.pop()
        else:
            path.append(ele.lower())
            backtrack(idx + 1, path)
            path.pop()
            path.append(ele.upper())
            backtrack(idx + 1, path)
            path.pop()
            
    n = len(s)
    res = []
    backtrack(0, [])
    return res

两个代码示例都是回溯，还是我应该将第一个称为 DFS 而将第二个称为回溯？

Answer 1

使用回溯（以及大多数递归函数），每个函数调用的关键不变性是它不会破坏父调用中的状态。

这应该具有直观意义，因为递归依赖于自相似性。如果在影响与祖先调用共享的数据结构的调用堆栈中的其他地方发生不可预测的状态更改，很容易看出自相似性的属性是如何丢失的。

递归函数调用的工作方式是将一个帧推送到 call stack，根据需要在本地操作状态，然后弹出调用堆栈。在返回到父框架之前，子调用负责恢复状态，以便从父调用框架的角度来看，执行可以继续进行，而不会被链下的一些随机祖先调用进行任何令人惊讶的状态修改。

打个比方，通过The Cat in the Hat or Risky Business的剧情，你可以把每个call frame想象成一个运行，主角（在他们的call frame中）搞得一团糟，然后必须恢复秩序在故事结束之前（函数returns）。

现在，鉴于这个高级目标，有多种方法可以实现它，如您的代码片段所示。一种方法是分配某种数据结构，例如列表对象一次，然后在每个调用帧上分配 push (append) 和 pop，镜像调用堆栈。

另一种方法是在产生子调用时复制状态，这样每个帧都会收到相关数据的新版本，并且它们所做的修改不会破坏它们的父状态。与改变单个数据结构相比，这通常需要更少的簿记，并且可能更不容易受到细微错误的影响，但由于内存分配器和垃圾收集器操作以及为每一帧复制数据结构，往往会产生更高的开销。

简而言之，不要混淆每个调用框架保持状态完整的高级目标和代码如何实现它。

就 backtracking versus DFS 而言，我认为回溯是一种专门的 DFS，它 p运行离开搜索树的分支，启发式确定不值得进一步探索，因为它们无法引导到一个解决方案。和以前一样，代码实际上如何实现状态恢复以实现回溯（复制数据结构或 pushing/popping 显式堆栈）不应该改变它是相同的基本算法技术的事实。

我见过术语“回溯”适用于像这样的排列算法。虽然这个术语可能相当普遍，但它似乎是一种误用，因为置换算法是一个全状态递归遍历，它总是会访问树中的所有节点，并且不会进行任何智能启发式 p运行ing就像回溯一样。

为什么回溯有时我们需要在递归后显式弹出，有时我们不需要？

Why for backtracking sometimes we need to explicitly pop after recursion, and sometimes we don't?

algorithm

depth-first-search

backtracking

recursive-backtracking