1. question: 全排列II（中等）
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/permutations-ii
示例 1：
1
2
3
4
5
| 输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
|
示例 2：
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
2
| 1 <= nums.length <= 8
-10 <= nums[i] <= 10
|
2. answers
这道题和全排列是类似的。只不过本题给定的数组中允许出现重复数字。那么此时和前面的子集组合类似，不同组合就可能出现重复，因此在同一个元素的不同选择的时候，需要判断是否和以前的选择重复。
因为是排列，并不是序列，所以数组中的元素的相对位置可以改变，因此可先对数组进行排序，然后在选择的时候，重复元素只能出现在相邻位置，此时可进行判断是否和上一位元素重复。
另外，传入下一个元素的所有选择仍然和全排列题一样。代码如下所示：
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| public class Solution_0089 {
public List<List<Integer>> result = new ArrayList<>();
public LinkedList<Integer> group = new LinkedList<>();
public void recurPmtUnique(int[] nums, ArrayList<Integer> list) {
if(group.size() == nums.length) {
result.add(new ArrayList<>(group));
return;
}
for (int i = 0; i < list.size(); i++) {
if(i > 0 && nums[list.get(i)] == nums[list.get(i-1)]) continue;
group.add(nums[list.get(i)]);
ArrayList<Integer> temp = new ArrayList<>(list);
temp.remove(i);
recurPmtUnique(nums, temp);
group.removeLast();
}
}
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
arrayList.add(i);
}
recurPmtUnique(nums,arrayList);
return result;
}
public static void main(String[] args) {
System.out.println();
int[] nums = {1, 2, 3};
Solution_0089 s = new Solution_0089();
List<List<Integer>> result = s.permuteUnique(nums);
for(List<Integer> list: result) {
for(Integer i: list)
System.out.print(i + "\t");
System.out.println();
}
}
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
