題目描述

給定一個可包含重復數(shù)字的序列，返回所有不重復的全排列。

示例1：

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

思路

1.這道題的思路與 46.全排列II是類似的，我們多結(jié)果進行去重處理即可。

Java代碼實現(xiàn)

    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);
        }
    }