【Leetcode 每日一题】47. 全排列 II

问题背景

给定一个可包含重复数字的序列 $nums$，按任意顺序 返回所有不重复的全排列。

数据约束

• $1\le nums.length\le 8$
• $-10\le nums[i]\le 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;}}
}