Python中用栈弹出实现回溯求无重复数组排列遇问题求助

嘿，我看了你用回溯法求全排列的代码，确实能看出你已经get了回溯的核心思路，但几个细节没处理好导致输出不对。咱们一步步来梳理问题：

问题分析 #

你现在得到的输出是[[1], [1], [2], [2], [3], [3]]，核心问题出在这几个地方：

1. 直接添加列表引用到结果集，后续修改破坏已保存结果 #

当你在if all(visited):分支执行results.append(temp)时，你添加的是temp这个列表的引用，而非它的独立副本。后面的temp.pop()操作会直接修改已经存在于results里的列表，所以最终所有结果都会变成pop后的短列表。

2. 主函数初始化逻辑冗余且逻辑断裂 #

你在主函数里循环每个元素，手动初始化temp并添加第一个元素再调用helper。这不仅做了重复工作，还导致回溯的起始状态不一致——主函数里没有标记对应元素为已访问（虽然helper开头补了，但逻辑上不该这么拆分），而且这种方式会让每个起始元素单独走一次回溯，其实回溯应该从空的temp开始，由helper自己遍历所有可能的起始选择。

3. Helper函数的参数设计没必要 #

你给_helper传了参数i，但其实helper只需要遍历所有未被访问的元素即可，不需要指定某个固定的i，这会限制回溯的灵活性。

修正后的代码 #

咱们把这些问题逐个修复：

class Solution(object):
    def permute(self, nums):
        visited = [False] * len(nums)
        results = []
        # 直接从空temp开始调用helper，不需要手动循环初始化
        self._helper(nums, visited, results, [])
        return results

    def _helper(self, nums, visited, results, temp):
        # 当temp长度等于nums长度时，说明找到一个全排列
        if len(temp) == len(nums):
            # 添加temp的副本，避免后续修改影响结果
            results.append(temp.copy())
            return
        
        for j in range(len(nums)):
            if not visited[j]:
                # 标记为已访问，加入当前路径
                visited[j] = True
                temp.append(nums[j])
                # 递归探索下一个元素
                self._helper(nums, visited, results, temp)
                # 回溯：撤销当前选择
                temp.pop()
                visited[j] = False

nums = [1, 2, 3]
a = Solution()
print(a.permute(nums))

代码修正说明 #

• 添加列表副本到结果集：用temp.copy()或者list(temp)创建新列表，确保后续的pop操作不会修改已经保存的结果。
• 简化主函数逻辑：直接从空的temp开始调用helper，让helper自主处理所有起始元素的选择，避免冗余循环。
• 优化终止条件：用len(temp) == len(nums)代替all(visited)，逻辑更直观，也省去了遍历整个visited数组的开销。
• 移除冗余参数：删掉不必要的i参数，让helper专注于遍历所有未访问元素，符合回溯的通用逻辑。

运行修正后的代码，就能得到预期的输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]啦。

内容的提问来源于stack exchange，提问作者Jonathon.lau