首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >全排列

全排列

作者头像
WindRunnerMax
发布于 2020-08-27 10:56:05
发布于 2020-08-27 10:56:05
1.1K0
举报
文章被收录于专栏:Czy‘s BlogCzy‘s Blog

全排列

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

示例

代码语言:javascript
复制
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

题解

代码语言:javascript
复制
/**
 * @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,以此类推。

代码语言:javascript
复制
   1         2          3
 2   3     1   3      1   2
3     2   3     1    2     1

每日一题

代码语言:javascript
复制
https://github.com/WindrunnerMax/EveryDay

题源

代码语言:javascript
复制
https://leetcode-cn.com/problems/permutations/
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-06-21 ,如有侵权请联系 cloudcommunity@tencent.com 删除
目录
  • 全排列
    • 示例
    • 题解
    • 思路
    • 每日一题
    • 题源
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档