回溯算法递归后有时需显式pop有时无需的原因及代码分类辨析

一、为什么回溯递归后有时需要pop操作，有时不需要？ #

核心原因是传递给下一层递归的路径对象是否为独立副本：

• 第一种写法中每次递归调用时传递的是sub + 新字符，Python中字符串是不可变对象，拼接操作会生成全新的字符串，上下两层递归的sub完全独立互不影响，相当于自动完成了状态隔离，不需要手动撤销操作。
• 第二种写法中传递的是列表path的引用，列表是可变对象，上下层操作的是同一个列表。递归返回后如果不执行pop撤销上一步的append操作，当前层的path状态就会被之前的分支污染，无法正确尝试其他可选分支，因此必须手动pop回退状态。

二、两段代码是否都属于回溯算法？ #

两段代码都属于回溯算法，不需要将第一段归为DFS、第二段归为回溯：
回溯的核心特征是「尝试某一分支→遍历完分支后回退状态→尝试其他分支」，本质是带状态回退的深度优先搜索。显式写pop只是状态回退的实现方式之一，第一种写法通过创建新对象实现了隐式的状态隔离，自动完成了回退逻辑，完全符合回溯的定义。

两种实现的优劣势对比 #

• 隐式传副本的写法代码更简洁，不容易出现状态回退的bug，但每次创建新对象会带来额外的内存和性能开销，适合小规模数据场景。
• 显式pop的写法复用同一个可变对象，内存效率更高，适合大规模数据场景，但需要手动维护状态回退逻辑，漏写pop很容易出现结果错误。

代码示例 #

不带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

内容的提问来源于stack exchange，提问作者illuminato