题目描述

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

示例1：

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

思路

1.这道题的思路与 46.全排列II是类似的，我们多结果进行去重处理即可。

Java代码实现

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            cur.add(nums[i]);
        }
        backtrack(res,cur,cur.size(),0);
        Set<List<Integer>> set = new HashSet<>(res);
        return new ArrayList<>(set);
    }
    
    private void backtrack(List<List<Integer>> res,List<Integer> cur,int n,int first){
        if(n == first){
            res.add(new ArrayList<>(cur));
            return ;
        }
        for(int i=first;i<n;i++){
            Collections.swap(cur,i,first);
            backtrack(res,cur,n,first+1);
            Collections.swap(cur,i,first);
        }
    }