Leetcode hot100 回溯

全排列

给定一个不含重复数字的数组 nums​ ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入： nums = [1,2,3]
输出： [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

‍

示例 2：

输入： nums = [0,1]
输出： [[0,1],[1,0]]

示例 3：

输入： nums = [1]
输出： [[1]]

题目描述

给定一个不含重复数字的数组 nums​ ，请返回所有可能的全排列。

示例:

• 输入：[1,2,3]​
• 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]​

思路

采用回溯法 (Backtracking)：

1. 定义一个 DFS 函数，通过逐步应用 nums 中的数字构造排列。
2. 通过 if 条件 item not in output​ 确保各个数字只使用一次，避免重复。
3. 当构造完整排列后，保存一份副本到结果集合。
4. 通过 output.pop()​ 完成回退，完成所有路径的遍历。

代码

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []  # 用于存储所有排列结果
        
        def dfs(output):
            # 如果当前排列的长度等于原始数组长度，说明构造出一个完整排列
            if len(output) == len(nums):
                result.append(output[:])  # 保存当前排列的副本（防止后续回溯修改）
                return
            
            # 遍历所有数字，尝试将未出现过的数字添加到当前排列中
            for item in nums:
                if item not in output:  # 跳过已经添加的数字，确保不重复
                    output.append(item)  # 做选择
                    dfs(output)          # 递归进入下一层
                    output.pop()         # 撤销选择（回溯）

        dfs([])  # 从空排列开始 DFS 搜索
        return result  # 返回所有可能的全排列

复杂度

时间复杂度：O(n × n!)​

• ​n!​ 是排列的总数，每次顺序都需要 O(n)​ 时间处理。

空间复杂度：

• 不计结果：O(n)​ (最深跳递调用堆栈)
• 如计入结果：O(n × n!)​

可能的优化

• 用一个 used​ 标记数组代替 item not in output​，减少 in 操作的运算处理时间
• 如果有重复元素，需要先排序 + 分支跳过重复

其他

• 这类问题很適合练习回溯思想和路径遍历
• 同类题目如：启用组合、N Queens、分组等

‍