题目描述
给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
样例
输入: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]]
算法1
(DFS + 回溯) $O(n * n!)$
从上面这张图可以看出,如果nums 数组是[1,2,3] 的话,那么对应的全排列可以通过如上的形式全部列出来,这种形式是通过 枚举每一个数组的值来展开的。
根据图,再按照代码逻辑走一遍。就会发现一个特点:每一次循环都是在寻找数组中的数是否能够加入到path 中,然后每次加入到path 中以后就进入到递归,此时index + 1,index 代表着递归的深度,并且index 和num.length 的关系是:当index == nums.length 时,说明此时递归的深度已经达到了nums.length 了,那么就说明之前的递归中已经把答案都放入到path 中,此时只需要把path 中的答案放入到res 中即可。
每一次循环都是为了从数组中找到可以加入到path 中的值,找到以后就进入到递归,递归完以后就进行回溯。当我们看到第一次调用dfs(…) 的时候,就说明以nums 数组第一个数值作为开始进行组合(递归)。 以第一个数作为开头递归完成以后,又回到第一次循环中,此时对第一个数进行回溯; 然后执行第二次for 循环,那么这一次for 循环中就会以nums 数组的第二个数作为开头进行组合(递归),当以第二数作为开头的组合(递归)完成以后,对第二个数进行回溯;接着进行第3 轮for 循环,即以nums 数组的第3 个数作为开头来进行组合(递归)…
时间复杂度
O(n * n!)
参考文献
https://www.bilibili.com/video/BV1M4411Q7td
https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
Java 代码
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] st;
public List<List<Integer>> permute(int[] nums) {
//特判
if(nums.length == 0) return null;
st = new boolean[nums.length];
dfs(nums,0);
return res;
}
//index:用于记录递归的深度,这个深度 == 遍历nums 的长度
void dfs(int[] nums,int index){
if(nums.length == index){
res.add(new ArrayList<>(path));
return;
}
for(int i = 0; i < nums.length; i++){
if(!st[i]){
//说明nums[i]没有被用过
//此时就把这个元素加入到path 容器中
path.add(nums[i]);
st[i] = true; //说明i 这个位置的元素已经被使用过了
//进行递归
dfs(nums,index+1);
//回溯
path.remove(path.size()-1);
st[i] = false;
}
}
}