酒类产品网站设计企业建站平台
问题背景
给定一个可包含重复数字的序列 n u m s nums nums，按任意顺序 返回所有不重复的全排列。
数据约束
- 1 ≤ n u m s . l e n g t h ≤ 8 1 \le nums.length \le 8 1≤nums.length≤8
- − 10 ≤ n u m s [ i ] ≤ 10 -10 \le nums[i] \le 10 −10≤nums[i]≤10
解题过程
这题和 全排列 的区别在于数组里可能有重复的元素，那么只要在回溯的过程中及时地跳过重复元素即可。
用哈希表来记录哪些位置上的元素已经添加到路径中了，遇到重复元素必须先填前面的元素。
具体实现
class Solution {public List<List<Integer>> permuteUnique(int[] nums) {Arrays.sort(nums);int n = nums.length;List<List<Integer>> res = new ArrayList<>();List<Integer> path = Arrays.asList(new Integer[nums.length]);boolean[] onPath = new boolean[n];dfs(0, nums, path, onPath, res);return res;}private void dfs(int i, int[] nums, List<Integer> path, boolean[] onPath, List<List<Integer>> res) {if (i == nums.length) {res.add(new ArrayList<>(path));return;}for (int j = 0; j < nums.length; j++) {if (onPath[j] || j > 0 && nums[j] == nums[j - 1] && !onPath[j - 1]) {continue;}path.set(i, nums[j]);onPath[j] = true;dfs(i + 1, nums, path, onPath, res);onPath[j] = false;}}
}