LeetCode-46.全排列
题目描述
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例 1：
输入: [1,2,3]
输出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
解法一递归、回溯
最重要的理解两个概念，一个是递归的递和归的过程，一个是回溯的思想。
递归：递归的过程中形成一个系统栈，分为递和归的过程， 函数调用之前的代码是递的过程执行的，函数调用之后的代码是归的过程执行的。
回溯：如执行时形成一个路径，当不能满足条件的时候再一步一步的回退回去 做操作 -> 递归 -> 撤销操作。
先看一下树形结构，此图来自 题解。
上图描述了一个递归的过程和回溯的过程，在每次遍历的时候，找到一个不重复的值，然后继续递归直到条件结束，然后在归的过程中回溯到上次值，再次查找不同的值。
举例 [1, 2, 3] 现在需要遍历每一个元素，每遍历一个元素如果没有就收集起来(temp = [])就递归继续查找。
- 第一层递归的循环；
i = 0, temp = [1]往下递归；此时还有i = 1、i = 2未执行。 - 第二层递归的循环：
1已经存在跳过本次继续i = 1, temp = [1, 2]往下递归；此时还有i = 2未执行。 - 第三层递归的循环：
1、2已经存在跳过本次继续i = 2, temp = [1, 2, 3]往下递归；此时没有可执行。 - 第四层递归：每次递归开始判断了数量是否足够，这里已经完成了一个组合
[1, 2, 3]收集起来直接返回，循环就不执行了。开始了归 + 回溯的过程。 - 第三层递归的回溯：撤回一步
temp = [1, 2]，没有循环完成。 - 第二层递归的回溯里的循环：撤回一步
temp = [1]，此时i = 2还可以继续执行。i = 2, temp = [1, 3]往下递归；此时没有可执行。- 第一层递归的循环：
1已经存在跳过本次继续i = 1, temp = [1, 3, 2]往下递归。 - 第一层递归：又得到了一个组合
[1, 3, 2]收集起来直接返回。开始了归 + 回溯的过程。 - 第一层递归的回溯：撤回一步
temp = [1, 3]，没有循环完成。
- 第一层递归的循环：
- 第二层递归的回溯：撤回一步
temp = [1]，没有循环完成。 - 第一层递归的回溯：撤回一步
temp = []，此时还有i = 1、i = 2可执行。 - 以下逻辑就会按照以上逻辑再走两遍。
- ...
代码实现
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function (nums) {
let list = []; // 结果集合
let temp = []; // 临时集合
let flag = 0;
function backtrack() {
flag++;
// 当排完一个组合，收集结果。开始 归 的过程。
if (temp.length === nums.length) {
return list.push([...temp]);
}
for (let i = 0; i < nums.length; i++) {
// 如果已经存在了，下一次循环跳过
if (temp.includes(nums[i])) continue;
// 收集元素
temp.push(nums[i]);
console.log(`递-${flag}-${i}`, temp);
backtrack(temp);
// 回溯的过程：删除一个回到上次，对应 push 操作。
temp.pop();
console.log(`归-${flag}-${i}`, temp);
}
}
backtrack();
return list;
};
// ===================================================================
// ========================== @test ==================================
// ===================================================================
console.log(permute([1, 2, 3]));
// [
// [ 1, 2, 3 ],
// [ 1, 3, 2 ],
// [ 2, 1, 3 ],
// [ 2, 3, 1 ],
// [ 3, 1, 2 ],
// [ 3, 2, 1 ]
// ]