LeetCode#22括号生成：回溯函数中S.pop()的作用及列表引用疑问

我是算法新手，正在解决LeetCode第22题（括号生成），现有如下代码：

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def backtrack(S, left, right):
            if len(S) == 2 * n:
                ans.append(''.join(S))
                return
            if left < n:
                S.append('(')
                backtrack(S, left+1, right)
                S.pop()
            if right < left:
                S.append(')')
                backtrack(S, left, right+1)
                S.pop()

        backtrack([], 0, 0)
        return ans

我不理解为何回溯函数末尾需要执行S.pop()？我原本认为从回溯函数返回后，S会恢复到调用前的状态，因为进入新函数时会创建本地副本，当前函数对S的修改不会影响之前的函数。但实际测试发现返回后S的改动依然存在，请问S是否在generateParenthesis的所有相关函数中共享？

核心原因：列表是可变对象，传递的是引用而非副本 #

你之前的理解有误——Python里可变对象（比如列表、字典）作为参数传递时，传递的是对象的引用，而不是创建一个全新的本地副本。这意味着所有调用backtrack的函数，操作的都是同一个列表实例。

举个简单的例子就能明白：

def modify_list(lst):
    lst.append(1)

my_list = []
modify_list(my_list)
print(my_list)  # 输出 [1]，原列表被直接修改了

回到你的括号生成代码：

• 当你执行S.append('(')时，这个操作直接改变了列表的内容，随后调用的递归backtrack(S, left+1, right)，操作的还是这个已经被修改的列表。
• 递归调用完成返回后，如果不执行S.pop()，刚才添加的'('会一直留在列表里，后续尝试添加右括号时，就会基于这个被修改的状态继续生成，最终得到错误的括号组合。

S.pop()的作用就是撤销当前选择：把刚才添加的括号从列表中移除，让列表回到调用append之前的状态，这样才能切换到下一种可能的选择（比如先探索完左括号的分支后，回到起点再探索右括号的分支）。

回溯算法的核心逻辑就是「做出选择→递归探索所有可能→撤销选择」，pop()正是实现「撤销选择」的关键步骤，保证每个分支探索完成后，能回到正确的初始状态去尝试其他路径。

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