46. 全排列

---

题目

描述： 给定一个不含重复数字的数组 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]]

---

解题思路

核心方法

回溯法：

1. 路径选择：维护一个临时列表 temp，存储当前已选择的数字。
2. 状态标记：使用布尔数组 isUsed 标记数字是否已被选择，避免重复使用。
3. 递归终止条件：当临时列表的长度等于数组长度时，将其加入结果列表。
4. 回溯过程：遍历所有未被选择的数字，将其加入临时列表，标记为已使用，递归进入下一层；递归返回后，将该数字从临时列表中移除，标记为未使用，继续尝试其他选择。

---

代码实现

回溯法（Java）

import java.util.*;

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    
    public List<List<Integer>> permute(int[] nums) {
        boolean[] isUsed = new boolean[nums.length];
        dfs(nums, 0, isUsed);
        return ans;
    }
    
    public void dfs(int[] nums, int depth, boolean[] isUsed) {
        if (depth == nums.length) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!isUsed[i]) {
                temp.add(nums[i]);
                isUsed[i] = true;
                dfs(nums, depth + 1, isUsed);
                isUsed[i] = false;
                temp.remove(temp.size() - 1);
            }
        }
    }
}

---

复杂度分析

• 时间复杂度：O(n * n!)，其中 n 是数组的长度。全排列的数量为 n!，每个排列需要 O(n) 的时间复制到结果列表中。
• 空间复杂度：O(n)，递归栈的深度为 n，临时列表和标记数组的空间也为 n。

---

总结

1. 回溯法是解决全排列问题的经典方法，通过递归和状态回溯，能够高效生成所有可能的排列。
2. 布尔数组 isUsed 确保了每个数字只被使用一次，避免了重复排列。
3. 该方法适用于不含重复元素的数组，若数组包含重复元素，需要额外的去重逻辑。

---