给定一个可包含重复数字的序列 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 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 }
提交反馈
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 }
提交反馈
原文：https://www.cnblogs.com/pengsay/p/14771807.html