47.全排列II

题目描述

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

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

Golang代码实现

func permuteUnique(nums []int) [][]int {
    sort.Ints(nums)
    res := make([][]int,0)
    permuteUniqueBackTrace(nums,0,&res)
    return res
}

func permuteUniqueBackTrace(nums []int,index int,res *[][]int){
    if index == len(nums){
        cur := make([]int,len(nums))
        copy(cur,nums)
        *res = append(*res,cur)
        return
    }

    numMap := make(map[int]int)

    for i := index; i<len(nums); i++{
        if _,ok := numMap[nums[i]];ok{
            continue
        }
        swap(nums,i,index)
        permuteUniqueBackTrace(nums,index+1,res)
        swap(nums,index,i)
        numMap[nums[i]] = index
    }

}

func swap(nums []int,left int,right int){
    temp := nums[left]
    nums[left] = nums[right]
    nums[right] = temp
}