回溯-排列
图解
复杂度
-
时间复杂度：
O(n*n!)，其中 n 为序列的长度； -
空间复杂度：
O(n)，其中 n 为序列的长度，除答案数组以外，递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，这里可知递归调用深度为O(n)；
代码实现
function backtrack(list, temp, nums) {
// 终止条件
if (temp.length === nums.length) {
return list.push([...temp]); // 存放结果
}
for (let i = 0; i < nums.length; i++) {
// 找到一个不在 temp 里的数字（这里用数组的 api 可以判断是否重复，重复节点不放入 tmp）
if (temp.includes(nums[i])) continue;
temp.push(nums[i]); // 放进去一个元素
backtrack(list, temp, nums); // 执行递归公式
temp.pop(); // 撤回这个元素
}
}
var permute = function (nums) {
let list = [];
backtrack(list, [], nums);
return list;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
进阶技巧🕴️ fetch 实现超时处理
上一篇
评论
