题目描述
给定一个可包含重复数字的序列 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
优化思路——前提是一定要先排序，即保证序列是有序的
如果前面有数，前一个数跟当前数相同，且前一个数没有用过，那么当前数也不能用。
递归+set集合去重
1 class Solution {
2 private int[] dp = new int[10];
3 private List<List<Integer>> lists = new ArrayList<>();
4 private Set<List<Integer>> set = new HashSet<>();
5
6 public List<List<Integer>> permuteUnique(int[] nums) {
7 dfs(nums, 0, new ArrayList<>());
8 for (List<Integer> temp : set) {
9 lists.add(temp);
10 }
11 return lists;
12 }
13
14 public void dfs(int[] nums, int pos, List<Integer> newList) {
15 if (pos == nums.length) {
16 set.add(new ArrayList<>(newList));
17 return;
18 }
19 for (int i = 0; i < nums.length; i ++) {
20 if (dp[i] == 0) {
21 dp[i] = 1;
22 newList.add(nums[i]);
23 // 递归
24 dfs(nums, pos + 1, newList);
25 newList.remove(newList.size() - 1);
26 // 回溯
27 dp[i] = 0;
28 }
29 }
30 }
31 }
提交反馈
递归+dp数组优化（在每次循环的时候就过滤掉重复排列的情况）
1 class Solution {
2
3 private int[] dp = new int[10];
4 private List<List<Integer>> lists = new ArrayList<>();
5
6 public List<List<Integer>> permuteUnique(int[] nums) {
7 // 排序
8 Arrays.sort(nums);
9 dfs(nums, 0, new ArrayList<>());
10 return lists;
11 }
12
13 public void dfs(int[] nums, int pos, List<Integer> newList) {
14 if (pos == nums.length) {
15 // 这里一定要注意：重新new一个新的集合，然后将newList作为参数传入，不然会有问题
16 lists.add(new ArrayList<>(newList));
17 return;
18 }
19 for (int i = 0; i < nums.length; i ++) {
20 if (dp[i] == 0) {
21 // 如果前面有数，如果前一个数跟当前数相同，且前一个数没有用过，那么当前数也不能用
22 if (i > 0 && nums[i] == nums[i - 1] && dp[i - 1] == 0) {
23 continue;
24 }
25 dp[i] = 1;
26 newList.add(nums[i]);
27 // 递归
28 dfs(nums, pos + 1, newList);
29 newList.remove(newList.size() - 1);
30 // 回溯
31 dp[i] = 0;
32 }
33 }
34 }
35 }
提交反馈