LeetCode高频题46. 全排列

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题

---

文章目录

• LeetCode高频题46. 全排列
• • @[TOC](文章目录)
• 题目
• 一、审题
• DFS枚举所有数字开头的情况，然后恢复现场，尝试别的数字做开头的情况
• 你也可以暴力试试：贼慢
• 总结

题目

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

DFS呗，还要剪枝，恢复现场

---

一、审题

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：

输入：nums = [1]
输出：[[1]]

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

DFS枚举所有数字开头的情况，然后恢复现场，尝试别的数字做开头的情况

本题老油条了
（1）每个i位置的数字做一次开头，它只能跟j=i–N-1每个位置交换一次【包括i自己哦！！！】
（2）剩下的数，又当一个新的数组，递归干这件事（1）
（3）直到i越界，此时的arr数组就是一个答案，收集放入ans，返回上一级，恢复现场，上次你怎么交换的，这次给我换回来，方便我尝试别的情况

举例：
arr=a b c
dfs的函数f，来到i=0位置，它可以跟谁交换？j=i–N-1，也就是它可以跟0 1 2 都交换一次
（1）i=0跟j=0交换，等于没换，arr=abc不动
然后，继续递归，i来到i+1=1处，i=1可以跟谁交换？j=1,2交换，它跟j=1交换试试，等于没换arr=abc
继续递归，i来到i+1=2处，i=2可以跟谁交换？j=2交换，它跟j=2交换试试，等于没换arr=abc
继续递归，i来到i+1=3处，i=3越界，收集答案，ans加一个arr就是当前的第一个排列结果
ans=abc

然后，返回上一级，恢复现场，i=2可以跟谁交换？j=2交换，它跟j=2交换试试，arr=abc
i来到i+1=1处，i=1可以跟谁交换？j=1,2交换，它跟j=2交换试试，arr=acb
继续递归，i来到i+1=2处，i=2可以跟谁交换？j=2交换，它跟j=2交换试试，等于没换arr=acb
继续递归，i来到i+1=3处，i=3越界，收集答案，ans加一个arr就是当前的第2个排列结果
ans=abc,acb

然后，返回上一级，恢复现场，i=2可以跟谁交换？j=2交换，它跟j=2交换试试，arr=acb
i来到i+1=1处，i=1可以跟谁交换？j=1,2交换，上面都换过了！，arr=acb
然后，返回上一级，恢复现场，刚刚1 2交换，现在2 1交换，arr=abc
然后，返回上一级，恢复现场，刚刚0 0交换，现在0 0交换，arr=abc
ans=abc,acb

现在基本就回到了当初i=0那会的情况，dfs的函数f，来到i=0位置，它可以跟谁交换？j=i–N-1，也就是它可以跟0 1 2 都交换一次
（2）i=0跟j=1交换【上面是先跟0交换的，你看看区别哦】，arr=bac，已经不再是abc了哦
其实又把上面的（1）走一遍
来到i=1位置，i可以跟j=1,2交换一次
i先跟1交换，就是自己bac
来到i=2位置，i可以跟j=2交换一次，没变，就是自己bac
来到i=3位置，i越界，ans加此时的arr，bac
ans=abc,acb,bac

返回i=2恢复现场，返回i=1，恢复现场，arr=bac
来到i=1位置，i可以跟j=1,2交换一次
i跟2交换，arr=bca
来到i=2位置，i可以跟j=2交换一次，没变，就是自己bca
来到i=3位置，i越界，ans加此时的arr，bca
ans=abc,acb,bac,bca

返回i=2恢复现场，arr=bca，返回i=1，恢复现场，arr=bac
返回i=0，恢复现场，arr=abc

（3）i=0跟j=2交换【上面是先跟0，再跟1交换的，你看看区别哦，现在是i=0与j=2交换】，arr=cba，已经不再是abc了哦
其实又把上面的（1）走一遍

来到i=1位置，i可以跟j=1,2交换一次
i=1跟j=1交换，arr=cba，
来到i=2位置，i可以跟j=2交换一次，arr=cba
来到i=3位置，越界，收集答案cba
ans=abc,acb,bac,bca,cba
返回i=2位置，恢复现场，arr=cba
返回i=1位置，恢复现场，arr=cba
来到i=1位置，i可以跟j=1,2交换一次
i=1跟j=2交换，arr=cab
来到i=2位置，i可以跟j=2交换一次，arr=cab
来到i=3位置，越界，收集答案cab
ans=abc,acb,bac,bca,cba,cab

返回i=2，恢复现场，arr=cab
返回i=1，恢复现场，arr=cba
返回i=0，恢复现场，arr=abc
结束！

ans=abc,acb,bac,bca,cba,cab就是所有的排列组合
a=1，b=2，c=3，就是本题的最优解，我们不浪费交换，也不会多找结果，也不会缺少结果！

我们就干一件事！
来此来到i，让i和j=i–N-1交换一次，剩下的数字继续递归i+1位置，但是干的事情，又是这个递归
不断往下，基本就让所有的数字做了开头，然后还考虑别的数字依次做了开头的情况
就是排列组合，每个数字做一次开头，剩下的数字继续缩短长度，又玩一次每个数字做一次开头，这样枚举下去
直到i越界，收集此刻的arr
返回上一层，你上次怎么交换的，给我换回来，恢复现场，我方便在i-1层继续让i和别的j位置交换，让另外的j来做排头
这样才公平

刚刚开始看很难，但是手撕一次代码，你基本就熟悉了

手撕代码！

        public void swap(int[] arr, int i, int j){
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

        //复习：依次从arr的i位置决定谁做排头，然后去i+1继续做决定
        public void f(int[] arr, int i, List<List<Integer>> ans){
            //直到i越界，收集此刻的arr
            if (i == arr.length){
                //每次都要把arr转List
                List<Integer> cur = new ArrayList<>();
                for(Integer x : arr) cur.add(x);//全部加入
                ans.add(cur);//作为一个排列组合结果，放入ans
            }else {//没有越界，决定让i跟谁换？
                //来此来到i，让i和j=i--N-1交换一次，剩下的数字继续递归i+1位置，但是干的事情，又是这个递归
                for (int j = i; j < arr.length; j++) {
                    swap(arr, i, j);
                    //不断往下，基本就让所有的数字做了开头，然后还考虑别的数字依次做了开头的情况
                    //就是排列组合，每个数字做一次开头，剩下的数字继续缩短长度，
                    // 又玩一次每个数字做一次开头，这样枚举下去
                    f(arr, i + 1, ans);
                    //返回上一层，你上次怎么交换的，给我换回来，恢复现场，
                    // 我方便在i-1层继续让i和别的j位置交换，让另外的j来做排头
                    swap(arr, j, i);
                }
            }
        }

        //主函数，就从i=0开始调用递归
        public List<List<Integer>> permuteReview(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();

            //从i=0开始决定谁做排头，收集一波答案
            f(nums, 0, ans);

            return ans;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

测试：

    public static void test(){
        int[] arr = {1,2,3};
        Solution solution = new Solution();
        List<List<Integer>> res = solution.permute(arr);
        for(List<Integer> list : res){
            for(Integer i : list) System.out.print(i +" ");
            System.out.println();
        }

        System.out.println();
        res = solution.permuteReview(arr);
        for(List<Integer> list : res){
            for(Integer i : list) System.out.print(i +" ");
            System.out.println();
        }

    }

    public static void main(String[] args) {
        test();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

问题不大：

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 2 1 
3 1 2 

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 2 1 
3 1 2 
1
2
3
4
5
6
7
8
9
10
11
12
13

LeetCode测试：

你也可以暴力试试：贼慢

枚举arr中的每一位置i
把每个数i加到path中，然后把arr中的这个数i删除，从新递归收集剩下的情况
当剩下的arr为null了，说明path就是一种排列组合

（1）比如arr=1 2 3
先加1到path，path=1
然后将arr中的1抹掉，arr=2 3
再递归去（1）
arr=2 3
先加2到path，path=1,2
然后将arr中的2抹掉，arr=3
再递归去（1）
arr=3
先加3到path，path=1,2,3
然后将arr中的3抹掉，arr=null
收集ans=path=123

然后从新考虑
（1）arr=1 2 3
先加2到path，path=2
然后将arr中的1抹掉，arr=1 3
再递归去（1）
arr=1 3
先加1到path，path=21
然后将arr中的1抹掉，arr=3
再递归去（1）
arr=3
先加3到path，path=213
然后将arr中的3抹掉，arr=null
收集ans=path=123,213

然后从新考虑……

这样子暴力递归，也可以，但是非常耗费时间

你只需要搞懂上面的交换，恢复现场，让每个i做一次排头就行。

---

总结

提示：重要经验：

1）来此来到i，让i和j=i–N-1交换一次，剩下的数字继续递归i+1位置，但是干的事情，又是这个递归
不断往下，基本就让所有的数字做了开头，然后还考虑别的数字依次做了开头的情况
就是排列组合，每个数字做一次开头，剩下的数字继续缩短长度，又玩一次每个数字做一次开头，这样枚举下去
直到i越界，收集此刻的arr
返回上一层，你上次怎么交换的，给我换回来，恢复现场，我方便在i-1层继续让i和别的j位置交换，让另外的j来做排头
这样才公平
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。