47. 全排列 II (opens new window)

解题思路：dfs+回溯

1.使用Set去重

HashMap记录每个数字出现的频次，keySet()去重

class Solution {
    Map<Integer, Integer> hashmap = new HashMap<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            hashmap.put(nums[i], hashmap.getOrDefault(nums[i], 0) + 1);
        }
        dfs(res, path, nums);
        return res;
    }

    public void dfs(List<List<Integer>> res, List<Integer> path, int[] nums) {
        for (Integer integer : hashmap.keySet()) {
            if (hashmap.get(integer) == 0) {
                continue;
            }
            path.add(integer);
            hashmap.put(integer, hashmap.get(integer) - 1);
            if (path.size() == nums.length) {
                List<Integer> pathres = new ArrayList<>(path);
                res.add(pathres);
                hashmap.put(integer, hashmap.get(integer) + 1);
                path.remove(path.size() - 1);
                return;
            }
            dfs(res, path, nums);
            hashmap.put(integer, hashmap.get(integer) + 1);
            path.remove(path.size() - 1);
        }
    }
}

2.排序+使用位数组去重

提前对数组排序，并用一个数组保存每个位置上的使用状态。

去重逻辑：在生成同一个位置的数字中，当前数字和前一个数字相同，并且前面那个数字的使用位为0，那么当前位置就可以跳过。因为只要满足上面条件，说明当前这个数字在本轮循环的前面已经被用过了。(注意，如果前一个数字使用位为1，那么说明当前数字在本轮循环还没有用过)

综上，剪枝过程分为两种情况：

• 当前使用位为1。说明在几轮循环已经被用过了。
• 本轮循环的去重判断。

class Solution {
    public  List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        int[] used=new int[nums.length];
        Arrays.sort(nums);
        dfs(res, path, nums,used);
        return res;
    }
    public  void dfs(List<List<Integer>> res, List<Integer> path, int[] nums,int[] used) {
        for (int i=0;i<nums.length;i++) {
            if (used[i]==1||(i-1>=0&&nums[i]==nums[i-1]&&used[i-1]==0)) {
                continue;
            }
            path.add(nums[i]);
            used[i]=1;
            if (path.size() == nums.length) {
                List<Integer> pathres = new ArrayList<>(path);
                res.add(pathres);
                used[i]=0;
                path.remove(path.size() - 1);
                return;
            }
            dfs(res, path, nums,used);
            used[i]=0;
            path.remove(path.size() - 1);
        }
    }
}