题解 | #有重复项数字的全排列#

package main

import (
	"sort"
)

/**
 * 给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。
 * 
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return int整型二维数组
 */
func permuteUnique( nums []int ) [][]int {
    // write code here
    sort.Ints(nums)
    var res [][]int
    backtrackUnique(nums,[]int{},&res,make([]bool, len(nums)))
    return res
}
func backtrackUnique(nums []int ,path []int, res *[][]int,used []bool) {
    if len(nums) == len(path) {
        temp := make([]int, len(nums))
        copy(temp, path)
        *res = append(*res, temp)
        return
    }

    for i := 0; i < len(nums);i++ { 
        // 确保当我们遇到一个与前一个元素相同的元素的时，
        // 我们只会在前一个元素已经被选取的情况下才会考虑选取当前元素。
        // !used[i-1] 避免回溯阶段的重复排列
        if used[i] || (i > 0 && nums[i] == nums[i -1] && !used[i - 1]) {
            continue
        }
        path = append(path, nums[i])
        used[i] = true
        backtrackUnique(nums, path, res, used)
        // 回溯
        path = path[:len(path) -1]
        used[i] = false
    }
}