题目
给定一个可包含重复数字的序列,返回所有不重复的全排列。
代码
Set 去重(运行时间 9ms)
class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> res = new ArrayList<>(); dfs(nums, 0, res); return res; } private void dfs(int[] nums, int index, List<List<Integer>> res) { if (index == nums.length - 1) { res.add(Arrays.stream(nums).boxed().collect(Collectors.toList())); } Set<Integer> set = new HashSet<>(); for (int i = index; i < nums.length; i++) { if (set.contains(nums[i])) continue; set.add(nums[i]); swap(nums, i, index); dfs(nums, index + 1, res); swap(nums, i, index); } } private void swap(int[] nums, int i, int j) { if (i == j) return; int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }
回溯搜索+剪枝(运行时间 2ms)
class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> res = new ArrayList<>(); int n = nums.length; if (n == 0) return res; Arrays.sort(nums); boolean[] used = new boolean[n]; Deque<Integer> path = new ArrayDeque<>(); dfs(nums, n, 0, used, path, res); return res; } private void dfs(int[] nums, int len, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res) { if (depth == len) { res.add(new ArrayList<>(path)); return; } for (int i = 0; i < len; i++) { if (used[i]) { continue; } if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { continue; } path.addLast(nums[i]); used[i] = true; dfs(nums, len, depth + 1, used, path, res); used[i] = false; path.removeLast(); } } }