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

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

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

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

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

打个比方，您可以将每个调用框架视为《戴帽子的猫》或《冒险生意》情节的一次贯穿，其中主角（在他们的调用框架中）弄得一团糟，然后必须在故事结束之前恢复秩序（函数返回）。

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

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

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

就回溯与DFS而言，我认为回溯是一种专门的 DFS，它会修剪掉启发式确定不值得进一步探索的搜索树分支，因为它们无法得出解决方案。和以前一样，代码如何实际实现状态恢复以实现回溯（复制数据结构或推送/弹出显式堆栈）不应改变它是相同基本算法技术的事实。

我见过术语“回溯”应用于这样的排列算法。尽管该术语可能相当常见，但它似乎是一种误用，因为排列算法是一种全状态递归遍历，它将始终访问树中的所有节点，并且不会像回溯那样进行任何智能启发式修剪。