学习记录：js算法（八十三）：全排列

全排列

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

思路一：回溯法

function permute(nums) {const res = [];const backtrack = (path, options) => {if (options.length === 0) {res.push([...path]);return;}for (let i = 0; i < options.length; i++) {// 选择const num = options[i];path.push(num);// 构建下一层决策树const nextOptions = [...options.slice(0, i), ...options.slice(i + 1)];backtrack(path, nextOptions);// 回溯path.pop();}};backtrack([], nums);return res;
}

讲解
对于这道题，我们想要生成所有可能的全排列，可以看作是从剩余的未选数字中每次选择一个数字，直到所有数字都被选完为止。具体步骤如下：

1. 初始化：创建一个空的路径数组 path 来存储当前的排列，以及一个空的结果数组res来存储所有有效的排列。
2. 递归函数：定义一个递归函数backtrack，它接受以下参数：
   ○ 当前路径path，
   ○ 剩余可选数字的集合options。
3. 基本结束条件：如果options集合为空，这意味着我们已经选择了一个全排列，此时将当前路径path拷贝一份加入结果数组res，然后返回。
4. 回溯过程：对于options集合中的每一个数字，执行以下操作：
   ○ 将当前数字添加到路径path中。
   ○ 从options集合中移除当前数字。
   ○ 递归调用backtrack函数，传递更新后的path和options。
   ○ 回溯，即将当前数字从路径path中移除，并将它放回·options·集合中。
5. 开始回溯：调用backtrack函数，传入初始的path和options。
6. 返回结果：最后返回结果数组res。

思路二：交换法

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;
};

讲解

1. 定义一个递归函数 backtrack(start)，其中 start 表示当前正在处理的元素的索引。
2. 如果 start 等于数组的长度，说明已经生成了一个完整的排列，将其添加到结果集中。
3. 否则，遍历从 start 到数组末尾的每个元素，对每个元素进行以下操作
   ○ 交换当前元素 nums[start] 和 nums[i]（i 从 start 到数组末尾）。
   ○ 调用递归函数 backtrack(start + 1) 继续处理下一个索引。
   ○ 在递归返回后，撤销交换，以恢复原数组的状态。
4. 运行示例
   ○ 假设输入数组为 [1, 2, 3]，运行过程如下：
   ○ 初始状态：[1, 2, 3]
   ○ 第一次调用 backtrack(0)，交换 1 和 1，继续递归。
   ○ 进入 backtrack(1)，交换 2 和 2，继续递归。
   ○ 进入 backtrack(2)，交换 3 和 3，得到排列 [1, 2, 3]，加入结果。
   ○ 撤销交换，返回到 backtrack(1)，交换 2 和 3，得到排列 [1, 3, 2]，加入结果。
   ○ 撤销交换，返回到 backtrack(0)，交换 1 和 2，继续递归。
   ○ 依此类推，最终得到所有可能的排列。

思路三：动态规划

var permute = function (nums) {const result = [];const dp = (arr) => {if (arr.length === 0) return [[]];const res = [];for (let i = 0; i < arr.length; i++) {const remaining = arr.slice(0, i).concat(arr.slice(i + 1));const perms = dp(remaining);for (const perm of perms) {res.push([arr[i], ...perm]);}}return res;};return dp(nums);
};

讲解

1. 定义一个递归函数 dp(arr)，该函数接受一个数组 arr 作为参数。
2. 如果 arr 为空，返回一个包含空数组的数组 [[]]，表示只有一种排列（空排列）。
3. 否则，遍历 arr 中的每个元素，将当前元素 arr[i] 取出，并对剩余元素 remaining 进行递归调用，生成所有可能的排列。
4. 对于每个生成的排列，将当前元素插入到每个可能的位置，从而形成新的排列。
5. 运行示例
   ○ 假设输入数组为 [1, 2, 3]，运行过程如下：
   ○ 初始调用 dp([1, 2, 3])。
   ○ 取出 1，剩余元素为 [2, 3]，递归调用 dp([2, 3])。
   ○ 对 [2, 3]，取出 2，剩余为 [3]，递归调用 dp([3])。
   ○ 对 [3]，返回 [[3]]（基础情况）。
   ○ 得到排列 [2, 3] 和 [3, 2]。
   ○ 将 1 插入到这两个排列中，得到 [1, 2, 3] 和 [1, 3, 2]。
   ○ 继续处理 2，取出 2，剩余为 [1, 3]，递归调用 dp([1, 3])。
   ○ 依此类推，最终得到所有可能的排列。

思路四：迭代法

var permute = function (nums) {let result = [[]];for (const num of nums) {const newResult = [];for (const perm of result) {for (let i = 0; i <= perm.length; i++) {newResult.push([...perm.slice(0, i), num, ...perm.slice(i)]);}}result = newResult;}return result;
};

讲解

1. 初始化：
   let result = [[]]，初始化结果数组 result，开始时只有一个空排列。这是构建全排列的基础。
   2.外层循环：
   for (const num of nums)，遍历输入数组 nums 中的每个数字 num。对于每个数字，我们都会生成新的排列。
2. 新结果数组：
   const newResult = []，每次处理一个新数字时，创建一个新的结果数组 newResult，用于存储包含当前数字的所有新排列。
3. 内层循环：
   • for (const perm of result)：遍历当前 result 中的每个排列 perm。
   • for (let i = 0; i <= perm.length; i++)：对于每个排列，尝试在不同的位置插入当前数字 num。这里的i 表示插入的位置，范围从 0 到 perm.length（即在排列的开头和结尾也可以插入）。
4. 生成新排列：
   newResult.push([...perm.slice(0, i), num, ...perm.slice(i)])：使用数组的 slice 方法生成新的排列。perm.slice(0, i) 取出 perm 中从开头到 i 的元素，num 是要插入的当前数字，perm.slice(i) 取出 perm 中从 i 开始到结束的元素。通过 展开运算符 ... 将这些部分组合成一个新的数组，并将其添加到 newResult 中。
5. 更新结果：
   result = newResult：在内层循环结束后，将 result 更新为 newResult，以便在下一次迭代中使用新的排列集合。
6. 返回结果：
   return result：最后返回包含所有全排列的数组 result。