LeetCode 46回溯法求排列：递归逻辑理解困惑求助

先把你贴的代码放出来：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

        results = []
        if len(nums) == 1:
            return [nums[:]]
        
        for _ in range(len(nums)):
            n = nums.pop(0)
            perms = self.permute(nums)

            for perm in perms:
                perm.append(n)
            
            results.extend(perms)
            nums.append(n)
        
        return results

你的误区在于对perms的修改时机理解错了，咱们一步步干运行permute([1,2,3])的过程，就能看明白：

1. 第一次调用permute([1,2,3])：

   • 进入循环，第一次迭代：
     • n = nums.pop(0) → n=1，此时nums变为[2,3]
     • 调用permute([2,3])，进入这个子函数：
       • 子函数里len(nums)=2≠1，进入循环：
         • 第一次迭代：n=2，nums变为[3]
         • 调用permute([3])，触发base case，返回[[3]]
         • 遍历perms（也就是[[3]]），每个perm追加2 → perms变成[[3,2]]
         • results.extend(perms) → 子函数的results现在是[[3,2]]
         • nums.append(2) → nums变回[3,2]
       • 第二次迭代：n=3，nums变为[2]
         • 调用permute([2])，返回[[2]]
         • 遍历perms，每个perm追加3 → perms变成[[2,3]]
         • results.extend(perms) → 子函数的results现在是[[3,2],[2,3]]
         • nums.append(3) → nums变回[2,3]
       • 子函数permute([2,3])返回[[3,2],[2,3]]
     • 回到上层函数，遍历返回的perms，每个perm追加1 → perms变成[[3,2,1],[2,3,1]]
     • results.extend(perms) → 上层的results现在是[[3,2,1],[2,3,1]]
     • nums.append(1) → nums变回[2,3,1]

2. 上层函数的第二次循环迭代：

   • n = nums.pop(0) → n=2，nums变为[3,1]
   • 调用permute([3,1])，这个过程和permute([2,3])完全一致，最终返回[[1,3],[3,1]]
   • 给每个perm追加2 → perms变成[[1,3,2],[3,1,2]]
   • results.extend(perms) → 上层results变为[[3,2,1],[2,3,1],[1,3,2],[3,1,2]]
   • nums.append(2) → nums变回[3,1,2]

3. 上层函数的第三次循环迭代：

   • n = nums.pop(0) → n=3，nums变为[1,2]
   • 调用permute([1,2])返回[[2,1],[1,2]]
   • 给每个perm追加3 → perms变成[[2,1,3],[1,2,3]]
   • results.extend(perms) → 最终results就是所有6种排列：[[3,2,1],[2,3,1],[1,3,2],[3,1,2],[2,1,3],[1,2,3]]

你之前误以为results.extend()会把修改前的perms和修改后的一起加进去，但实际上，在执行for perm in perms: perm.append(n)之后，perms本身已经被修改成带n的数组了，所以results.extend(perms)添加的是修改后的版本，而不是原版本加修改版。这就是你预期和实际结果不一样的核心原因。

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