一起学习LeetCode热题100道（55/100）

55.全排列(学习)

给定一个不含重复数字的数组 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 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

解析：
一、初始化：
1.定义一个结果数组 result 来存储所有生成的排列。
2.定义一个 backtrack 函数来实现回溯逻辑。该函数接受一个参数 first，表示当前正在填充的排列的起始位置。

二、回溯逻辑：
1.基准情况：如果 first 等于 nums 的长度，说明当前排列已经被填满，是一个有效的排列，将其添加到 result 中。注意，这里我们需要2.复制 nums 的当前状态，因为 nums 会被修改，而我们希望在结果中保留每个排列的原始数据。
3.递归遍历：从 first 开始遍历 nums，对于每个位置 i，执行以下操作：
3.1.将 nums[first] 和 nums[i] 交换，这样可以确保在递归调用 backtrack(first + 1) 时，nums[first] 被视为当前位置的已选元素。
3.2.递归调用 backtrack(first + 1) 来填充下一个位置。
3.3.在递归返回后，撤销上一步的交换操作，以便 nums 可以恢复到交换前的状态，用于尝试其他排列。

三、执行回溯：
1.从位置 0 开始调用 backtrack(0)，以生成所有排列。

四、返回结果：
1.当所有可能的排列都被生成并添加到 result 后，返回 result。

var permute = function (nums) {const result = [];const backtrack = (first) => {// 所有数都填完了  if (first === nums.length) {result.push([...nums]); // 注意这里需要拷贝一份nums，否则后续修改会影响结果  }for (let i = first; i < nums.length; i++) {// 动态维护数组  [nums[first], nums[i]] = [nums[i], nums[first]]; // 交换  // 继续递归填下一个数  backtrack(first + 1);// 撤销操作  [nums[first], nums[i]] = [nums[i], nums[first]]; // 交换回来  }};backtrack(0);return result;
};