46. 全排列

题目描述

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

输入输出

1
2
3
4
5
6
7
8
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

输入:nums = [0,1]
输出:[[0,1],[1,0]]

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

基本思路

回溯算法讲解:labuladong LeetCode-liweiwei讲解

1
2
3
4
5
6
7
8
9
10
# 回溯-代码模板
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择

要点:

  • 每一个结点表示了求解全排列问题的不同的阶段,这些阶段通过变量的「不同的值」体现,这些变量的不同的值,称之为「状态」;
  • 使用深度优先遍历有「回头」的过程,在「回头」以后, 状态变量需要设置成为和先前一样 ,因此在回到上一层结点的过程中,需要撤销上一次的选择,这个操作称之为「状态重置」;
  • 深度优先遍历,借助系统栈空间,保存所需要的状态变量,在编码中只需要注意遍历到相应的结点的时候,状态变量的值是正确的,具体的做法是:往下走一层的时候,path 变量在尾部追加,而往回走的时候,需要撤销上一次的选择,也是在尾部操作,因此 path 变量是一个栈;
  • 深度优先遍历通过「回溯」操作,实现了全局使用一份状态变量的效果。

设计状态变量:

  • 首先这棵树除了根结点和叶子结点以外,每一个结点做的事情其实是一样的,即:在已经选择了一些数的前提下,在剩下的还没有选择的数中,依次选择一个数,这显然是一个 递归 结构;
  • 递归的终止条件是: 一个排列中的数字已经选够了 ,因此我们需要一个变量来表示当前程序递归到第几层,我们把这个变量叫做 depth,或者命名为 index ,表示当前要确定的是某个全排列中下标为 index 的那个数是多少;
  • 布尔数组 used,初始化的时候都为 false 表示这些数还没有被选择,当我们选定一个数的时候,就将这个数组的相应位置设置为 true ,这样在考虑下一个位置的时候,就能够以 O(1) 的时间复杂度判断这个数是否被选择过,这是一种「以空间换时间」的思想。

性能分析:

  • 时间复杂度:$O(n \times!n)$ 不要求掌握 只需知道是阶乘倍
  • 空间复杂度:$O(n)$ 递归函数在递归过程中需要为每一层递归函数分配栈空间

java实现

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
class Solution {
public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
List<List<Integer>> result = new ArrayList<>();
if(len == 0) return result;
boolean[] used = new boolean[len];
List<Integer> path = new ArrayList<>();

backtrace(nums, len, 0, path, used, result);
return result;
}

public void backtrace(int[] nums, int len, int depth,
List<Integer> path, boolean[] used, List<List<Integer>> result){
if(depth == len){
result.add(new ArrayList<Integer>(path));
//result.add(path)会显示6个空的列表
//变量 path 所指向的列表在深度优先遍历的过程中只有一份,深度优先遍历完成以后回到了根结点,成为空列表。
//在 Java 中,参数传递是 值传递,对象类型变量在传参的过程中,复制的是变量的地址。这些地址被添加到 res 变量,但实际上指向的是同一块内存地址,因此我们会看到 6 个空的列表对象。解决的方法很简单,在 res.add(path); 这里做一次拷贝即可。

return;
}
for(int i = 0; i < len; i++){
if(!used[i]){
path.add(nums[i]);
used[i] = true;
backtrace(nums, len, depth+1, path, used, result);
used[i] = false;
path.remove(path.size() - 1);
}
}
}
}