百度&leetcode46：全排列问题

[sisterAn]

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
 [1,2,3],
 [1,3,2],
 [2,1,3],
 [2,3,1],
 [3,1,2],
 [3,2,1]
]

附赠leetcode地址：leetcode

[sisterAn]

本题是回溯算法的经典应用场景

1. 算法策略

回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。深度优先搜索利用的就是回溯算法思想。

2. 适用场景

回溯算法很简单，它就是不断的尝试，直到拿到解。它的这种算法思想，使它通常用于解决广度的搜索问题，即从一组可能的解中，选择一个满足要求的解。

3. 代码实现

我们可以写一下，数组 [1, 2, 3] 的全排列有：

• 先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列；
• 再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列；
• 最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列。

即回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

图片来自于：https://pic.leetcode-cn.com/0bf18f9b86a2542d1f6aa8db6cc45475fce5aa329a07ca02a9357c2ead81eec1-image.png

这显然是一个 递归 结构；

• 递归的终止条件是： 一个排列中的数字已经选够了 ，因此我们需要一个变量来表示当前程序递归到第几层，我们把这个变量叫做 depth ，或者命名为 index ，表示当前要确定的是某个全排列中下标为 index 的那个数是多少；
• used（object）：用于把表示一个数是否被选中，如果这个数字(num)被选择这设置为 used[num] = true ，这样在考虑下一个位置的时候，就能够以 O(1)的时间复杂度判断这个数是否被选择过，这是一种「以空间换时间」的思想。

let permute = function(nums) {
 // 使用一个数组保存所有可能的全排列
 let res = []
 if (nums.length === 0) {
 return res
 }
 let used = {}, path = []
 dfs(nums, nums.length, 0, path, used, res)
 return res
}
let dfs = function(nums, len, depth, path, used, res) {
 // 所有数都填完了
 if (depth === len) {
 res.push([...path])
 return
 }
 for (let i = 0; i < len; i++) {
 if (!used[i]) {
 // 动态维护数组
 path.push(nums[i])
 used[i] = true
 // 继续递归填下一个数
 dfs(nums, len, depth + 1, path, used, res)
 // 撤销操作
 used[i] = false
 path.pop()
 }
 
 }
}

4. 复杂度分析

• 时间复杂度： O(n∗n!)，其中 n 为序列的长度

  这是一个排列组合，每层的排列组合数为：A^m_n=n!/(n−m)! ，故而所有的排列有 ：

  A¹_n + A²_n + … + A^n-1_n = n!/(n−1)! + n!/(n−2)! + … + n! = n! * (1/(n−1)! + 1/(n−2)! + … + 1) <= n! * (1 + 1/2 + 1/4 + … + 1/2^n-1) < 2 * n!

  并且每个内部结点循环 n 次，故非叶子结点的时间复杂度为 O(n∗n!)

• 空间复杂度：O(n)

leetcode

[Jeckhenry]

const permMutation = function (arr) {
 let res = [];
 if (arr.length <= 1) {
 return arr;
 }
 for (let i = 0; i < arr.length; i++) {
 let indexStr = arr[i];
 let otherStr = [...arr.slice(0, i), ...arr.slice(i + 1)];
 let tmp = permMutation(otherStr);
 for (let j = 0; j < tmp.length; j++) {
 res.push(Array.prototype.flat.call([indexStr, tmp[j]], Infinity));
 }
 }
 return res;
 }

[marlboroKay]

var permute = function(nums) {
 let len = nums.length;
 if(len === 0) return [[]];
 let res = [];
 let perm = function(arr, p, q, res){
 if(p === q){
 res.push([...arr])
 }
 for(let i = p; i <= q; i++){
 swap(arr, i, p);
 perm(arr, p+1, q, res);
 swap(arr, i, p);
 }
 }
 let swap = function(arr, left, right){
 let temp = arr[left];
 arr[left] = arr[right];
 arr[right] = temp;
 }
 perm(nums, 0, len-1, res)
 return res;
};

[marlboroKay]

题解
1.分析示列，不难发现全排列，首先将每个元素排到第一位。
2.剩余元素再重复第一步操作，依次处理各个元素。
3.通过1，2两步操作，可以利用递归实现操作，但是有个地方需要特别处理，就是对于移动的元素，
在递归操作之前，和之后该如何操作。
4.由此产生两种解决办法，一种是利用回溯，定义回溯状态标识，在递归操作完成后，重置状态
一种是利用swap函数（交换元素位置）；相对来说，swap函数更好理解一些；
5.递归函数实现：
递归终止条件：
1.swap
子全排列的数组长度等于nums的长度时，递归终止。
2.dfs
子全排列所在层数（depth）等于nums的长度时，递归终止。

循环数组内部元素：
1.swap
通过swap，将nums[i] 与 p(从0开始)交换
调用递归函数prem，传入 nums, p+1, nums.lenght, res（结果集）
递归内部可以理解为，例如1，2，3 先将1取出，求解剩余2，3 的全排列，依次类推
当递归终止后，再次调用swap函数，将数组重置成原始状态；

2.dfs
dfs函数中传入nums，len，depth（当前所在层数），path（存储当前排列结果的动态数组），
used（元素是否已存在排列中的布尔标识）， res（结果集）
调用递归dfs，判断当前元素是否在排列中used[i] === true ?，存在则跳过，不存在则
used[i] = true， 将当前nums[i] 存入path中，然后调用dfs
dfs终止后，***重点来了，回溯状态需要重置，used[i] = false，path.pop() 将当前元素从已有排列中删除

全排列属于回溯入门问题，回溯还是需要多学多练

swap解法

var permute = function(nums) {
 let len = nums.length;
 if(len === 0) return [[]];
 let res = [];
 let perm = function(arr, p, q, res){
 if(p === q){
 res.push([...arr])
 }
 for(let i = p; i < q; i++){
 swap(arr, i, p);
 perm(arr, p+1, q, res);
 swap(arr, i, p);
 }
 }
 let swap = function(arr, left, right){
 let temp = arr[left];
 arr[left] = arr[right];
 arr[right] = temp;
 }
 perm(nums, 0, len, res)
 return res;
};

dfs解法

var permute = function(nums) {
 let len = nums.length;
 if(len === 0) return [[]];
 let res = [];
 let path = []; //维护动态数组
 let used = {}; //保存已存在的元素
 let dfs = function(arr, len, depth, path, used, res){
 if(len === depth){
 res.push([...path]);
 return
 }
 for(let i = 0; i < len; i++){
 if(!used[i]){
 path.push(arr[i]);
 used[i] = true;
 dfs(arr, len, depth+1, path, used, res)
 //状态回溯
 used[i] = false;
 path.pop();
 }
 }
 }
 dfs(nums, len, 0, path, used, res);
 return res;
}

[DCbryant]

const permute = nums => {
const res = [];
const len = nums.length;
const curr = [];
const use = {};
if (curr.length === len) {
res.push(curr);
}

function dfs (nth) {
for (let i = 0; i < len; i++) {
if (!use[i]) {
use[i] = 1;
curr.push(nums[i]);
dfs(i);
curr.pop();
use[i] = 0;
}
}
}

dfs(0);
return res;
};

[syc666]

感觉递归函数不需参数也可以

function fn(arr) {
 const path = [], used = {}
 const res = []
 const loopFn = () => {
 if (path.length === arr.length) {
 res.push([...path])
 return
 }
 for (let i = 0, len = arr.length; i < len; i++){
 if (!used[i]) {
 path.push(arr[i])
 used[i] = true
 loopFn()
 path.pop()
 used[i] = false
 }
 }
 }
 loopFn()
 return res
}

[z253573760]

function bar(list) {
 const res = [];
 function dfs(arr = []) {
 if (arr.length === list.length) {
 res.push([...arr]);
 return;
 }
 for (const item of list) {
 if (arr.indexOf(item) === -1) {
 arr.push(item);
 dfs(arr);
 arr.pop();
 }
 }
 }
 dfs([]);
 return res;
}

const res = bar([1, 2, 3]);
console.log(res);

[fengmiaosen]

/**
 * 回溯算法
 * @param {number[]} nums 
 */
function permute(nums) {
 let res = []

 function dfs(track) {
 // 到达决策树底部
 if (track.length === nums.length) {
 res.push([...track])
 return
 }

 for (let num of nums) {
 // 剪枝操作，避免重复遍历
 if (track.includes(num)) {
 continue
 }

 track.push(num)

 dfs(track)

 track.pop()
 }
 }

 dfs([])

 return res
}

console.log(permute([1,2,3]));