思路

参考代码随想录给出的树形结构图：代码随想录-46.全排列

回溯三部曲

• 递归函数参数

排列的子集是有序的，对于集合 {1, 2} 和 {2, 1} 是两个不同的集合，这是与组合问题、子集问题不一样的地方。所以排列问题不需要考虑结果去重，在递归过程中不需要传入 start 来表示下一层递归的起始位置，因为每一层递归的 for 循环都是从 0 开始遍历。

当然，为了保证每层递归中横向遍历时不会出现同一个元素多次使用的情况，需要一个 bool 类型的 used 的数组，用来标记已经选择的元素，如上图中黄色部分展示。

代码如下：

path []int
result [][]int
used []bool

func dfs(nums []int){}

• 递归终止条件

全排列问题最终收集的结果是叶子节点，这和组合问题、分割问题一样。所以终止条件是遍历到叶子节点。当负责收集元素的数组 path 的长度达到原数组 nums 的长度时，就说明找到了一个全排列结果，此时也表示到达了叶子节点。

代码如下：

if len(path) == len(nums) {
    temp := make([]int, len(path))
    copy(temp, path)
    result = append(result, temp)
    return
}

• 单层搜索的逻辑

与组合问题、分割问题、子集问题最大的不同就是 for 循环中不再需要 start ，而是从 0 开始遍历。同时， used 数组用来记录此时的 path 中有哪些元素已经被使用，一个排列里一个元素只能使用一次。

代码如下：

for i := 0; i < len(nums); i++ {
    if used[i] == true {
        continue
    }
    path = append(path, nums[i])
    used[i] = true
    dfs(nums)
    path = path[:len(path)-1]
    used[i] = false
}

• 时间复杂度：O(n!)
• 空间复杂度：O(n)

完整代码如下：

var (
    path []int
    result [][]int
    used []bool
)

func permute(nums []int) [][]int {
    path = []int{}
    result = [][]int{}
    used = make([]bool, len(nums))
    dfs(nums)
    return result
}

func dfs(nums []int) {
    if len(path) == len(nums) {
        temp := make([]int, len(path))
        copy(temp, path)
        result = append(result, temp)
        return
    }

    for i := 0; i < len(nums); i++ {
        if used[i] == false {
            continue
        }
        path = append(path, nums[i])
        used[i] = true
        dfs(nums)
        path = path[:len(path)-1]
        used[i] = false
    }
}

思路

本题与 46.全排列 的区别就是数组 nums 中存在重复数字，而且要返回所有不重复的全排列。涉及到树层去重，在组合问题的 40.组合总和II 和子集问题的 90.子集II 中分别讲述了组合问题和子集问题的树层去重方法。

在排列问题中实现的逻辑也大差不差，都是先排序再通过 bool 类型的 used 数组来进行树层去重。

但是，有一个地方不一样。

对于组合问题和子集问题来说，需要 start 参数，for 循环是从 start 开始遍历，某个元素是否可以重复选取是通过 dfs(nums, i) 或者 dfs(nums, i+1) 来实现，前者表示该元素可以重复选取，后者表示该元素不可以重复选取。

排列问题不需要 start 参数，for 循环都是从 0 开始遍历，这就导致 dfs 参数里没有 start 可用，无法支持该元素是否可重复选取。因此，这就需要每次进入下一次递归之前都要判断当前元素是否已经被选取了，即判断 userd[i] == false 才可以进行下一轮递归。

回溯三部曲

• 递归函数参数

排列问题，不需要 start 参数，需要 used 数组来进行树层去重和避免使用同一个元素。

代码如下：

path []int
result [][]int
used []bool

func dfs(nums []int){}

• 递归终止条件

当负责收集元素的数组 path 的长度达到原数组 nums 的长度时，就说明找到了一个全排列结果，此时也表示到达了叶子节点。

代码如下：

if len(path) == len(nums) {
    temp := make([]int, len(nums))
    copy(temp, path)
    result = append(result, temp)
    return
}

• 单层搜索逻辑

for 循环从 0 开始遍历，used 数组实现树层去重以及避免重复使用同一个元素。

代码如下：

for i := 0; i < len(nums); i++ {
    if i > 0 && nums[i-1] == nums[i] && used[i-1] == false {
        continue
    }
    if used[i] == false {
        path = append(path, nums[i])
        used[i] = true
        dfs(nums)
        path = path[:len(path)-1]
        used[i] = false
    }
}

完整代码如下：

var (
	path   []int
	result [][]int
	used   []bool
)

func permuteUnique(nums []int) [][]int {
	path = []int{}
	result = [][]int{}
	used = make([]bool, len(nums))
	sort.Ints(nums)
	dfs(nums)
	return result
}

func dfs(nums []int) {
	if len(path) == len(nums) {
		temp := make([]int, len(path))
		copy(temp, path)
		result = append(result, temp)
		return
	}

	for i := 0; i < len(nums); i++ {
		if i > 0 && nums[i-1] == nums[i] && used[i-1] == false {
			continue
		}
		if used[i] == false {
			path = append(path, nums[i])
			used[i] = true
			dfs(nums)
			path = path[:len(path)-1]
			used[i] = false
		}
	}
}

• 时间复杂度：O(n!*n)
• 空间复杂度：O(n)