Leetcode全排列1-2题题解
对于全排列问题，可能我们很多人从小在数学课上都做过，并且都能由一定的规律将所有排列情况写出来，但如何用编码的方式求解此类问题成了我的问题，或许也成是你们还未解决的问题，其实这类问题的套路都是 dfs + 回溯算法，然后，根据题目要求进行剪枝，我将通过下面两题来讲解这类问题具体做法。
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
1
2
3
4
5
6
7
8
9
10
| 输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
|
题解（dfs，回溯算法）
分析：
由于是回溯算法，因此，会用到栈，通常我们所学的栈是这种用法 Stack<Integer> stack = new Stack<Integer>();,但在Stack的源码中发现了Deque<Integer> stack = new ArrayDeque<Integer>();这种用法，百度之后，知道了Deque : （double-ended queue，双端队列）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，相比list增加运算符重载。
具体步骤如下：
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
| class Solution {
public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList();
Deque<Integer> path = new ArrayDeque();
boolean[] used = new boolean[len];
dfs(nums,len,0,used,path,res);
return res;
}
public void dfs(int[] nums,int len,int depth,boolean[] used,Deque<Integer> path,List<List<Integer>> res){
if(depth == len){
res.add(new ArrayList(path));
return;
}
for(int i = 0 ; i < len; i++){
if(used[i]){
continue;
}
path.addLast(nums[i]);
used[i] = true;
dfs(nums,len,depth + 1,used,path,res);
path.removeLast();
used[i] = false;
}
}
}
|
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
1
2
3
4
5
6
7
| 输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
|
题解（dfs，回溯算法）
分析：
此题和全排列解法类似，唯一的差别在于可选数组nums中存在重复的数字，可能会产生重复的路径，因此，需要在判断当前数字是否用过后，再次判断上一次使用的数字和当前数字是否相同，如果相同，进行剪枝，具体差别见代码。
具体步骤如下：
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
39
40
41
42
43
44
| class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
int len = nums.length;
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList();
Deque<Integer> path = new ArrayDeque();
boolean[] used = new boolean[len];
dfs(nums,len,0,used,path,res);
return res;
}
public void dfs(int[] nums,int len,int depth,boolean[] used,Deque<Integer> path,List<List<Integer>> res){
if(depth == len){
res.add(new ArrayList(path));
return;
}
for(int i = 0 ; i < len; i++){
if(used[i]){
continue;
}
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
path.addLast(nums[i]);
used[i] = true;
dfs(nums,len,depth + 1,used,path,res);
path.removeLast();
used[i] = false;
}
}
}
|
:smile:以上题解仅限于个人理解，如有更好的方法或者更高效的解法，请移步至评论区，谢谢！
