LC46. 全排列

题目描述

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

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

思路解析

核心思路：回溯法。将排列问题看作在树形结构上深度优先搜索，每个节点代表一个部分排列，通过选择、递归、撤销选择来遍历所有可能。

关键点： 1. 使用一个布尔数组 used 标记数字是否已被使用，避免重复选取。 2. 递归终止条件：当前路径长度等于 nums 长度时，将当前路径的副本加入结果。 3. 每次递归从 nums 中选一个未使用的数字，加入路径，标记 used，递归，然后撤销选择。

易错点：

• 结果添加时需拷贝当前路径（如 new ArrayList<>(path)），否则后续修改会污染结果。