Permutations（全排列）

题目 / Problem

中文： 给定一个由互不相同的整数组成的数组 nums，返回其所有可能的全排列。答案可以按任意顺序返回。

English: Given an array nums of distinct integers, return all possible permutations. You may return the answer in any order.

示例 / Examples

Example 1

Input:  nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2

Input:  nums = [0,1]
Output: [[0,1],[1,0]]

Example 3

Input:  nums = [1]
Output: [[1]]

约束 / Constraints

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数互不相同。
All integers in nums are unique.

解题思路：回溯 / Approach: Backtracking

全排列要求每个数字在一个排列中恰好出现一次。我们可以逐个决定排列中每个位置放哪个数字：
A permutation uses every number exactly once. We can decide which number to place at each position one by one:

使用 path 保存当前正在构造的排列。
Use path to store the permutation currently being built.
使用 used[i] 表示 nums[i] 是否已经放入当前排列。
Use used[i] to record whether nums[i] is already in the current permutation.
每一层遍历所有尚未使用的数字，选择其中一个加入 path。
At each level, try every number that has not been used.
递归结束后撤销选择，让其他数字也能出现在当前位置。
Undo the choice after recursion so other numbers can occupy the same position.
当 path.length === nums.length 时，得到一个完整排列。
When path.length === nums.length, one complete permutation has been formed.

回溯模板 / Backtracking Template

选择一个未使用的数字
Choose an unused number
        ↓
加入当前排列，并标记为已使用
Add it to the path and mark it as used
        ↓
递归构造下一个位置
Build the next position recursively
        ↓
移除该数字，并恢复为未使用
Remove it and mark it as unused

题目保证所有数字互不相同，因此不需要额外处理相同数字造成的重复排列。
All values are distinct, so no extra duplicate-removal logic is needed.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function permute(nums) {
  const result = [];
  const path = [];
  const used = new Array(nums.length).fill(false);

  function backtrack() {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) {
        continue;
      }

      // 做出选择 / Make a choice
      path.push(nums[i]);
      used[i] = true;

      // 构造下一个位置 / Build the next position
      backtrack();

      // 撤销选择 / Undo the choice
      path.pop();
      used[i] = false;
    }
  }

  backtrack();
  return result;
}

执行过程 / Walkthrough

以 nums = [1,2,3] 为例：
For nums = [1,2,3]:

[]
├── [1]
│   ├── [1,2]
│   │   └── [1,2,3]
│   └── [1,3]
│       └── [1,3,2]
├── [2]
│   ├── [2,1]
│   │   └── [2,1,3]
│   └── [2,3]
│       └── [2,3,1]
└── [3]
    ├── [3,1]
    │   └── [3,1,2]
    └── [3,2]
        └── [3,2,1]

例如，从 [1,2,3] 返回时：
For example, when returning from [1,2,3]:

[1,2,3] → 移除 3 → [1,2]
[1,2]   → 移除 2 → [1]
[1]     → 选择 3 → [1,3]

这就是“尝试一个选择、递归、再撤销选择”的回溯过程。
This is the backtracking pattern: make a choice, recurse, and then undo the choice.

为什么要复制 `path`？ / Why Copy `path`?

path 在整个搜索过程中会不断被修改。如果直接执行 result.push(path)，结果数组中的元素会共同引用同一个数组。
path is continuously modified during the search. If we use result.push(path), every result entry will reference the same array.

因此，找到完整排列时必须保存它的副本：
Therefore, a copy must be stored whenever a complete permutation is found:

result.push([...path]);

复杂度 / Complexity

设 n = nums.length。共有 n! 个排列，每个排列需要复制 n 个元素。
Let n = nums.length. There are n! permutations, and copying each one takes O(n) time.

时间复杂度 / Time: O(n × n!)
辅助空间 / Auxiliary space: O(n)
结果空间 / Output space: O(n × n!)

辅助空间包括递归调用栈、path 和 used，不包括返回结果。
Auxiliary space includes the recursion stack, path, and used, excluding the returned result.

易错点 / Common Pitfalls

每层都应从下标 0 开始遍历，因为排列中的数字顺序不同也属于不同答案。
Start the loop from index 0 at every level because different orders are different permutations.
必须用 used 防止同一个数组元素在当前排列中被重复选择。
Use used to prevent selecting the same array element twice in one permutation.
递归返回后，要同时执行 path.pop() 和 used[i] = false。
After recursion, call both path.pop() and used[i] = false.
保存答案时要复制 path，不能直接保存其引用。
Copy path when saving a result instead of storing its reference.
本题输入元素互不相同；如果允许重复元素，还需要先排序并在同一层跳过重复选择。
Values are distinct here. If duplicates were allowed, sorting and same-level duplicate skipping would also be required.

Permutations