021-全排列（回溯法）

46. 全排列-Medium

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

示例 1：

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

方法 1：回溯法（经典解法）

核心思想

• 递归 + 回溯：每次选择一个未被使用的数字，放入当前路径，直到路径长度等于 nums.length。
• 维护 used 数组：记录哪些数字已经被使用过，避免重复选择。

JavaScript 代码

var permute = function(nums) {
    const result = [];
    const used = new Array(nums.length).fill(false); // 记录数字是否被使用
    
    const backtrack = (path) => {
        if (path.length === nums.length) {
            result.push([...path]); // 复制当前路径
            return;
        }
        
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue; // 跳过已使用的数字
            
            used[i] = true;       // 标记为已使用
            path.push(nums[i]);    // 加入当前路径
            backtrack(path);       // 递归
            path.pop();           // 回溯
            used[i] = false;      // 恢复状态
        }
    };
    
    backtrack([]);
    return result;
};

时间复杂度

• **O(n × n!)**：共有 n! 种排列，每种排列需要 O(n) 时间生成。

---

方法 2：交换法（更高效，原地修改）

核心思想

• 交换元素：通过交换 nums 中的元素，直接生成所有排列，无需 used 数组。
• 递归 + 回溯：固定一个位置，递归生成剩余部分的排列。

JavaScript 代码

var permute = function(nums) {
    const result = [];
    
    const backtrack = (start) => {
        if (start === nums.length) {
            result.push([...nums]); // 复制当前排列
            return;
        }
        
        for (let i = start; i < nums.length; i++) {
            [nums[start], nums[i]] = [nums[i], nums[start]]; // 交换
            backtrack(start + 1);                            // 递归
            [nums[start], nums[i]] = [nums[i], nums[start]]; // 恢复
        }
    };
    
    backtrack(0);
    return result;
};

时间复杂度

• **O(n!)**：比方法 1 稍快，但仍是指数级。

---

方法 3：库函数（Python 适用）

在 Python 中，可以直接用 itertools.permutations：

from itertools import permutations

def permute(nums):
    return list(permutations(nums))

但 JavaScript 没有内置排列函数，需手动实现。

---

变种问题：全排列 II（含重复数字）

如果 nums 包含重复数字，需去重：

var permuteUnique = function(nums) {
    nums.sort((a, b) => a - b); // 先排序
    const result = [];
    const used = new Array(nums.length).fill(false);
    
    const backtrack = (path) => {
        if (path.length === nums.length) {
            result.push([...path]);
            return;
        }
        
        for (let i = 0; i < nums.length; i++) {
            if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) {
                continue; // 跳过已使用或重复的数字
            }
            
            used[i] = true;
            path.push(nums[i]);
            backtrack(path);
            path.pop();
            used[i] = false;
        }
    };
    
    backtrack([]);
    return result;
};

关键点：

1. 排序：让相同数字相邻。
2. 去重条件：
   • nums[i] === nums[i - 1]：当前数字和前一个相同。
   • !used[i - 1]：前一个数字未被使用（避免重复选择）。

---

总结

方法	特点	时间复杂度	适用场景
回溯 + used 数组	直观，易理解	O(n × n!)	通用
交换法	更高效，原地修改	O(n!)	无需额外空间
库函数（Python）	代码最短	-	仅限 Python
全排列 II（去重）	需排序 + 去重逻辑	O(n × n!)	含重复数字

推荐：

• 无重复数字：交换法（方法 2）。
• 含重复数字：回溯 + 排序去重（方法 1 变种）。