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

package main

import "sort"

/**
 *
 * @param num int整型一维数组
 * @return int整型二维数组
 */

func permuteUnique(nums []int) [][]int {
    //1.对数字进行从小到大排列，那么相同的数字肯定相邻
    sort.Ints(nums)
	res := [][]int{}
	length := len(nums)
	if length == 0 {
		return res
	}
	path := []int{}
	used := make([]bool, length)
	dfs(nums, length, 0, &path, &used, &res)

	return res
}

func dfs(nums []int, length, depth int, path *[]int, used *[]bool, res *[][]int) {
	if length == depth {
		temp := []int{}
		temp = append(temp, *path...)
		*res = append(*res, temp)
	}
	for i := 0; i < length; i++ {
        //2 对于相同的数字只添加一次即可保证不重复
		if (*used)[i] || i > 0 && (*used)[i-1] && nums[i-1] == nums[i] {
			continue
		}
		*path = append(*path, nums[i])
		(*used)[i] = true
		dfs(nums, length, depth+1, path, used, res)
		*path = (*path)[:len(*path)-1]
		(*used)[i] = false
	}
}