二哥的 LeetCode 刷题笔记：046.全排列

作者：沉默王二
发布时间：2022-10-07T08:32:48.224+0800

---

046.全排列

题意

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

难度

中等

示例

示例 1：

输入：nums = [1,2,3]

示例 2：

输入：nums = [0,1]

示例 3：

输入：nums = [1]

分析

题意非常朴素，让我们找出nums的所有排列，那我们就来直观朴素的分析一下这道题。

首先我们来看看找出一个排列需要怎么做：

• 在所有的nums[i]中任意选择一个，加入list中
• 在所有的nums[i]中选择一个没有被第1步选择的数字，加入list中
• 在所有的nums[i]中选择一个没有被1,2步骤选择的数字，加入list中
• ....

以此类推，直到所有的数字都选择过，那么现在的list就是一个合法的排列，可以加入到答案中。

那么接下来就是把所有的排列都找出来，所以要在上述的枚举中，加入次序，这样子就可以保证我们能够枚举出所有答案，而不会因为 任意 而导致疏漏。

所以整个过程就如下：

• 选择nums[0]作为list的第一项
• 选择nums[1]作为list的第二项
• ......
• 选择nums[n - 2]作为list的第n - 1项
• 选择nums[n - 1]作为list的第n项
• 将此时的list加入答案
• list弹出nums[n - 1]
• list弹出nums[n - 2]
• 选择nums[n - 1]作为list的第n - 1项
• 选择nums[n - 2]作为list的第n项
• 将此时的list加入答案
• ......

以次类推，最终我们就可以把所有的排列都加入答案中。

来看代码，注释中有详细的说明。

class Solution {

    boolean[] vis;//表示nums[i]有没有被选择过    int[] numsIn;//全局变量，跟nums[]一样，为了访问方便，设置为全局变量
    private void DFS(List nowSta){        for(int i = 0;i < numsIn.length;i++){            if(!vis[i]){//从0-(nums.length-1)中选择一个没有用过的加入nowSta                vis[i] = true;//标记选择过                nowSta.add(numsIn[i]);//加入nowSta                if(nowSta.size() == vis.length) {//如果已经选择了足够多的，那么这就是答案                    res.add(new ArrayList<>(nowSta));                }                else {                    DFS(nowSta);//没选够则继续选择                }                nowSta.remove(nowSta.size() - 1);//将选择过的移除出nowSta，从而进行下次选择                vis[i] = false;//恢复标记            }        }    }    public List<List> permute(int[] nums) {        numsIn = nums;        List ans = new ArrayList<>();        vis = new boolean[nums.length];        for(int i = 0;i < nums.length;i++){            vis[i] = true;            ans.add(nums[i]);            if(ans.size() == vis.length) {                res.add(new ArrayList<>(ans));            }            else {                DFS(ans);            }            ans.remove(ans.size() - 1);            vis[i] = false;        }        return res;    }}

算法的时间复杂度嘛，大致为，n为nums的长度。因为第i次都需要从剩下的n - i + 1个元素中选择一个放入，而且最后将合法的排列加入答案也需要n的时间。但是因为这题有个条件1 <= nums.length <= 6，所以这个朴素的算法也可以跑出不错的成绩。

总结

其实有时候我们可以通过题目给的数据范围来判断题目所需要的算法，像这种比较小的数据范围，我们不妨大胆的去使用深度优先搜索，通过模拟来直接实现，而不用过分去考虑是否有更优的选择，先实现题目的要求再说。

力扣链接：https://leetcode.cn/problems/permutations/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 870 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

046.全排列

题意

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

难度

中等

示例

示例 1：

输入：nums = [1,2,3]

示例 2：

输入：nums = [0,1]

示例 3：

输入：nums = [1]

分析

题意非常朴素，让我们找出nums的所有排列，那我们就来直观朴素的分析一下这道题。

首先我们来看看找出一个排列需要怎么做：

• 在所有的nums[i]中任意选择一个，加入list中
• 在所有的nums[i]中选择一个没有被第1步选择的数字，加入list中
• 在所有的nums[i]中选择一个没有被1,2步骤选择的数字，加入list中
• ....

以此类推，直到所有的数字都选择过，那么现在的list就是一个合法的排列，可以加入到答案中。

那么接下来就是把所有的排列都找出来，所以要在上述的枚举中，加入次序，这样子就可以保证我们能够枚举出所有答案，而不会因为 任意 而导致疏漏。

所以整个过程就如下：

• 选择nums[0]作为list的第一项
• 选择nums[1]作为list的第二项
• ......
• 选择nums[n - 2]作为list的第n - 1项
• 选择nums[n - 1]作为list的第n项
• 将此时的list加入答案
• list弹出nums[n - 1]
• list弹出nums[n - 2]
• 选择nums[n - 1]作为list的第n - 1项
• 选择nums[n - 2]作为list的第n项
• 将此时的list加入答案
• ......

以次类推，最终我们就可以把所有的排列都加入答案中。

来看代码，注释中有详细的说明。

class Solution {

    boolean[] vis;//表示nums[i]有没有被选择过    int[] numsIn;//全局变量，跟nums[]一样，为了访问方便，设置为全局变量
    private void DFS(List nowSta){        for(int i = 0;i < numsIn.length;i++){            if(!vis[i]){//从0-(nums.length-1)中选择一个没有用过的加入nowSta                vis[i] = true;//标记选择过                nowSta.add(numsIn[i]);//加入nowSta                if(nowSta.size() == vis.length) {//如果已经选择了足够多的，那么这就是答案                    res.add(new ArrayList<>(nowSta));                }                else {                    DFS(nowSta);//没选够则继续选择                }                nowSta.remove(nowSta.size() - 1);//将选择过的移除出nowSta，从而进行下次选择                vis[i] = false;//恢复标记            }        }    }    public List<List> permute(int[] nums) {        numsIn = nums;        List ans = new ArrayList<>();        vis = new boolean[nums.length];        for(int i = 0;i < nums.length;i++){            vis[i] = true;            ans.add(nums[i]);            if(ans.size() == vis.length) {                res.add(new ArrayList<>(ans));            }            else {                DFS(ans);            }            ans.remove(ans.size() - 1);            vis[i] = false;        }        return res;    }}

算法的时间复杂度嘛，大致为，n为nums的长度。因为第i次都需要从剩下的n - i + 1个元素中选择一个放入，而且最后将合法的排列加入答案也需要n的时间。但是因为这题有个条件1 <= nums.length <= 6，所以这个朴素的算法也可以跑出不错的成绩。

总结

其实有时候我们可以通过题目给的数据范围来判断题目所需要的算法，像这种比较小的数据范围，我们不妨大胆的去使用深度优先搜索，通过模拟来直接实现，而不用过分去考虑是否有更优的选择，先实现题目的要求再说。

力扣链接：https://leetcode.cn/problems/permutations/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 870 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

046.全排列

题意

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

难度

中等

示例

示例 1：

输入：nums = [1,2,3]

示例 2：

输入：nums = [0,1]

示例 3：

输入：nums = [1]

分析

题意非常朴素，让我们找出nums的所有排列，那我们就来直观朴素的分析一下这道题。

首先我们来看看找出一个排列需要怎么做：

• 在所有的nums[i]中任意选择一个，加入list中
• 在所有的nums[i]中选择一个没有被第1步选择的数字，加入list中
• 在所有的nums[i]中选择一个没有被1,2步骤选择的数字，加入list中
• ....

以此类推，直到所有的数字都选择过，那么现在的list就是一个合法的排列，可以加入到答案中。

那么接下来就是把所有的排列都找出来，所以要在上述的枚举中，加入次序，这样子就可以保证我们能够枚举出所有答案，而不会因为 任意 而导致疏漏。

所以整个过程就如下：

• 选择nums[0]作为list的第一项
• 选择nums[1]作为list的第二项
• ......
• 选择nums[n - 2]作为list的第n - 1项
• 选择nums[n - 1]作为list的第n项
• 将此时的list加入答案
• list弹出nums[n - 1]
• list弹出nums[n - 2]
• 选择nums[n - 1]作为list的第n - 1项
• 选择nums[n - 2]作为list的第n项
• 将此时的list加入答案
• ......

以次类推，最终我们就可以把所有的排列都加入答案中。

来看代码，注释中有详细的说明。

class Solution {

    boolean[] vis;//表示nums[i]有没有被选择过    int[] numsIn;//全局变量，跟nums[]一样，为了访问方便，设置为全局变量
    private void DFS(List nowSta){        for(int i = 0;i < numsIn.length;i++){            if(!vis[i]){//从0-(nums.length-1)中选择一个没有用过的加入nowSta                vis[i] = true;//标记选择过                nowSta.add(numsIn[i]);//加入nowSta                if(nowSta.size() == vis.length) {//如果已经选择了足够多的，那么这就是答案                    res.add(new ArrayList<>(nowSta));                }                else {                    DFS(nowSta);//没选够则继续选择                }                nowSta.remove(nowSta.size() - 1);//将选择过的移除出nowSta，从而进行下次选择                vis[i] = false;//恢复标记            }        }    }    public List<List> permute(int[] nums) {        numsIn = nums;        List ans = new ArrayList<>();        vis = new boolean[nums.length];        for(int i = 0;i < nums.length;i++){            vis[i] = true;            ans.add(nums[i]);            if(ans.size() == vis.length) {                res.add(new ArrayList<>(ans));            }            else {                DFS(ans);            }            ans.remove(ans.size() - 1);            vis[i] = false;        }        return res;    }}

算法的时间复杂度嘛，大致为，n为nums的长度。因为第i次都需要从剩下的n - i + 1个元素中选择一个放入，而且最后将合法的排列加入答案也需要n的时间。但是因为这题有个条件1 <= nums.length <= 6，所以这个朴素的算法也可以跑出不错的成绩。

总结

其实有时候我们可以通过题目给的数据范围来判断题目所需要的算法，像这种比较小的数据范围，我们不妨大胆的去使用深度优先搜索，通过模拟来直接实现，而不用过分去考虑是否有更优的选择，先实现题目的要求再说。

力扣链接：https://leetcode.cn/problems/permutations/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 870 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412