一、简介

题目：全排列-47

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

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

二、实现

func permuteUnique(nums []int) [][]int {
    if len(nums) == 0 {
        return nil
    }

    // 排序，让相同的元素，在一起，便于过滤
    sort.Slice(nums, func (i,j int)bool {
        return nums[i] <= nums[j]
    })

    res := make([][]int, 0)
    doPermuteUnique(nums, []int{}, &res)

    return res
}

func doPermuteUnique(nums []int, curList []int, res *[][]int) {
    if len(nums) == 0 {
        c := make([]int, len(curList))
        copy(c, curList)

        *res = append(*res, c)

        return
    }

    for i:=0; i< len(nums); i++ {
        // 如果和前面一个元素相同，需要过滤
        if i >0 && nums[i] == nums[i-1] {
            continue
        }

        curList = append(curList, nums[i])
        if i == 0 {
            doPermuteUnique(nums[1:], curList, res)
        } else if i == len(nums) -1 {
            doPermuteUnique(nums[:len(nums) -1], curList, res)
        } else {
            newNums := make([]int, 0)
            newNums = append(newNums, nums[0:i]...)
            newNums = append(newNums, nums[i+1:]...)

            doPermuteUnique(newNums, curList, res)
        }

        curList = curList[:len(curList) -1]
    }
}