搜云库技术团队
全排列
给定一个没有重复 数字的序列，返回其所有可能的全排列。
示例
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
题解
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
var target = [];
recursive(nums, [], target, 0);
return target;
};
function recursive(nums, tmp, target, deep){
if(deep === nums.length) {
target.push([...tmp]);
return 0;
}
for(let i=0; i<nums.length; ++i) {
if(tmp.includes(nums[i])) continue;
tmp.push(nums[i]);
recursive(nums, tmp, target, deep+1);
tmp.pop();
}
}
思路
整体思路是利用回溯的方式，在具体递归的过程中类似于一棵决策树，首先定义一个用于递归的函数，分别传递原数组的引用、暂存数组的引用、目标数组的引用、递归深度，如果递归的深度与原数组的长度相同，那么就将暂存数组做一个浅拷贝push到目标数组并结束本次递归，如果递归深度还没有达到原数组长度，以[1, 2, 3]输入为例，在tmp数组为空的情况下，会有三种选择1、2、3，当第一次将1追加到tmp数组时，进行递归再次到循环，那么此时会选择第二位，此时为2，接下来进行第三位的选择，只能为3，此时在tmp数组即为[1, 2, 3]，再进行递归时即会触发边界条件，将tmp数组浅拷贝到target，然后tmp数组会出栈3，然后此时选择第三位的循环就结束了，本次递归完成，然后在选择第二位时的循环中i为1的递归也已经结束，tmp数组弹出2，此时循环到i为2，tmp数组进栈nums[2]即为3，那么第三位就只能选择2，tmp数组中就存在[1, 3, 2]并触发边界条件。简单来说就是在递归的过程中，第一位只能为1或2或3，当第一位为1时那么第二位只能为2或3，当第二位为2时第三位只能为3，第二位为3时第二位只能为2，以此类推。
1 2 3
2 3 1 3 1 2
3 2 3 1 2 1
每日一题
https://github.com/WindrunnerMax/EveryDay
题源
https://leetcode-cn.com/problems/permutations/
