题目难度：medium
掌握程度：🌟🌟🌟
47. 全排列 II - 力扣（LeetCode）
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8
-10 <= nums[i] <= 10
回溯，在全排列的基础上加了两个扩展，
- 输入数字有重复
- 结果需要不重复
需要想办法去重，有两个策略，直接暴力回溯，然后对结果直接进行一次去重即可
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
| class Solution {
private Set<List<Integer>> res;
private List<Integer> path;
private boolean[] visited;
public List<List<Integer>> permuteUnique(int[] nums) {
res = new HashSet<>();
path = new ArrayList<>();
visited = new boolean[nums.length];
backtrack(nums,nums.length);
return new ArrayList<>(res);
}
private void backtrack(int[] nums,int n){
if(path.size() == n){
res.add(new ArrayList<>(path));
return;
}
for(int i = 0 ; i < n ; i++){
if(!visited[i]){
path.add(nums[i]);
visited[i] = true;
backtrack(nums,n);
visited[i] = false;
path.remove(path.size()-1);
}
}
}
}
|
在不用 set 的情况下，如何去重
先看看是如何重复的 比如 [1,1,2], 重复的话，就会出现两个 [1,1,2]
考虑重复元素一定要 优先排序 ，将重复的都放在一起，便于找到重复元素和剪枝！！！
当前元素和前一个元素值相同（此处隐含这个元素的 index>0 ），并且前一个元素还没有被使用过的时候，我们要剪枝
即
1
2
3
| if(visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) ){
continue;
}
|
最后答案
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
| class Solution {
private List<List<Integer>> res;
private List<Integer> path;
private boolean[] visited;
public List<List<Integer>> permuteUnique(int[] nums) {
res = new ArrayList<>();
path = new ArrayList<>();
visited = new boolean[nums.length];
Arrays.sort(nums);
backtrack(nums,nums.length);
return res;
}
private void backtrack(int[] nums,int n){
if(path.size() == n){
res.add(new ArrayList<>(path));
return;
}
for(int i = 0 ; i < n ; i++){
if(visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) ){
continue;
}
path.add(nums[i]);
visited[i] = true;
backtrack(nums,n);
visited[i] = false;
path.remove(path.size()-1);
}
}
}
|
回溯排列的基础题目
46. 全排列 - 力扣（LeetCode）
回溯组合的基础题目
77. 组合 - 力扣（LeetCode）
排列与组合的主要差异在于
排列需要维护一个 visited[] 数组来标记当前元素是否已选择，组合需要在回溯过程中，控制选择区间