题目描述

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

分析

  1. 先将所有数从小到大排序，这样相同的数会排在一起；
  2. 从左到右依次枚举每个数，每次将它放在一个空位上；
  3. 对于相同数，我们人为定序，就可以避免重复计算：我们在dfs时记录一个额外的状态，记录上一个相同数存放的位置 start，我们在枚举当前数时，只枚举 start+1,start+2,…,n这些位置。
  4. 不要忘记递归前和回溯时，对状态进行更新。

贴出代码

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        dfs(list, nums,new boolean[nums.length]);
        return res;
    }

    private void dfs(ArrayList<Integer> list, int[] nums, boolean[] visit) {
        if (nums.length == list.size()){
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i ++){
            if (visit[i])
                continue;
            if (i > 0 && nums[i - 1] == nums[i] && !visit[i - 1])
                continue;
            list.add(nums[i]);
            visit[i] = true;
            dfs(list,nums,visit);
            visit[i] = false;
            list.remove(list.size() -1);
        }
    }
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄