全排列II(重复元素)
题目描述
给定一个可包含重复数字的序列，返回所有不重复的全排列。
实例
1
2
3
4
5
6
7
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
思路
大体思路与没有重复元素的全排列类似，但是需要去除重复的序列
res记录最后的结果path用来记录满足条件的序列used[ ]用来记录元素是否使用过- 需要对
num数组排序以便进行去重剪枝
当num中有重复元素的时候，只需要考虑一个，但是这是横向考虑，这样的话在迭代的时候肯定会收到影响，所以需要考虑前一个元素是否使用过，如果前一元素没有使用过则代表前一元素是刚回溯上来取消选择了，这时候就需要去重剪枝了。
图片来自LeetCode-liweiwei1419
代码实现
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
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> res;
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
res = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> path = new ArrayList<Integer>();
boolean[] used = new boolean[num.length];
if(num.length == 0){
return res;
}
Arrays.sort(num);
dfs(num, path, used);
return res;
}
private void dfs(int[] num, ArrayList<Integer> path, boolean[] used){
if(path.size() == num.length){
res.add(new ArrayList<Integer>(path));
return;
}
for(int i = 0; i < num.length; i++){
if(used[i]) {
continue;
}
if(i > 0 && num[i] == num[i - 1] && !used[i - 1] ) {
continue;
}
used[i] = true;
path.add(num[i]);
dfs(num, path, used);
//取消选择，向上回溯
path.remove(path.size() - 1);
used[i] = false;
}
}
}