LeetCode 46全排列：两种生成方式的对比与疑问

问题背景 #

给定不含重复整数的数组nums，返回所有可能的排列，顺序不限。

两种Python解法 #

解法1：显式回溯法 #

def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        N = len(nums)
        def dfs(subset, permutation: List[int]):
            if len(subset) == N:
                results.append(subset.copy())
                return
            for i, num in enumerate(permutation):
                subset.append(num)
                dfs(subset, permutation[:i] + permutation[i+1:])
                # backtracking
                subset.pop()
        dfs([], nums)
        return results

解法2：无显式回溯的递归法 #

def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        N = len(nums)
        def dfs(subset, permutation: List[int]):
            if len(subset) == N:
                results.append(subset.copy())
                return
            for i, num in enumerate(permutation):
                dfs(subset + [num], permutation[:i] + permutation[i+1:])
        dfs([], nums)
        return results

问题解答 #

1. 你的理解完全正确 #

• 解法1中，Python列表是可变对象，采用引用传递，append操作会修改同一个列表实例，因此必须通过pop进行显式回溯，否则后续迭代会错误复用已修改的列表，导致最终结果混乱。
• 解法2通过subset + [num]生成全新的列表传递给递归函数，每个递归分支的subset都是独立实例，无需手动回溯，因为原列表不会被修改。

2. 两种方式的适用场景与偏好 #

• 解法1的显式回溯更高效，复用同一个列表减少了大量列表拷贝开销，处理较大规模输入时性能更优，是回溯算法的经典实现，在算法竞赛、性能敏感场景中更受青睐。
• 解法2的代码更简洁直观，省去了回溯的pop步骤，可读性更强，适合快速实现和小规模场景，但每次递归创建新列表会带来额外内存开销和拷贝时间，输入规模较大时效率会明显下降。

3. 复杂度分析的准确性修正 #

• 时间复杂度：两种解法的时间复杂度应为O(N×N!)，而非你所说的O(N!)。总共有N!个排列，每个排列的构建需要O(N)的时间（填充长度为N的列表），因此总时间是两者的乘积，O(N!)的描述忽略了每个排列的构建成本，不够准确。
• 空间复杂度：
  • 解法1：不计结果存储时，空间复杂度为O(N)，主要来自递归栈深度（最多N层）和复用的subset列表；若包含结果存储，则为O(N×N!)。
  • 解法2：不计结果存储时，空间复杂度为O(N×N!)，因为每个递归调用都会生成新列表，总共有O(N!)个中间列表，每个列表平均长度为O(N)；包含结果存储时同样为O(N×N!)。

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