47.给定一个可能包含重复数字的集合，实现一个算法返回所有可能的唯一排列
package leetcode
import "sort"
/*
实现思路：
该问题要求生成一个包含重复元素数组的所有唯一排列。通过递归和回溯的方法构建排列，同时通过排序和跳过重复元素来避免生成重复的排列。具体方法是在递归过程中，当遇到与前一个元素相同且前一个元素未被使用的情况时，跳过该元素，确保相同元素在不同位置的处理一致。
关键点是使用排序和跳过重复元素的技巧。
*/
func permuteUnique(nums []int) [][]int {
// 边界条件判断，如果输入数组为空，直接返回空结果
if len(nums) == 0 {
return [][]int{}
}
// 排序是去重的关键步骤
sort.Ints(nums)
// 初始化用于存储中间状态的变量
used, p, res := make([]bool, len(nums)), []int{}, [][]int{}
// 开始生成排列
generatePermutation47(nums, 0, p, &res, &used)
// 返回最终结果
return res
}
// 递归生成排列的函数
func generatePermutation47(nums []int, index int, p []int, res *[][]int, used *[]bool) {
// 如果当前排列的长度与输入数组相等，表示找到一个完整排列
if index == len(nums) {
temp := make([]int, len(p))
copy(temp, p)
*res = append(*res, temp)
return
}
// 遍历数组，尝试每一个未被使用的元素
for i := 0; i < len(nums); i++ {
// 如果当前元素没有被使用
if !(*used)[i] {
// 如果当前元素与前一个元素相同，且前一个元素未被使用，跳过，避免重复
if i > 0 && nums[i] == nums[i-1] && !(*used)[i-1] {
continue
}
// 标记元素为已使用
(*used)[i] = true
// 将元素加入当前排列
p = append(p, nums[i])
// 递归调用，生成下一个元素的排列
generatePermutation47(nums, index+1, p, res, used)
// 回溯，撤销选择，继续尝试其他可能
p = p[:len(p)-1]
(*used)[i] = false
}
}
}
/*
性能分析：
时间复杂度：O(n * n!)，其中 n 是数组的长度。虽然存在去重的步骤，但在最坏情况下仍然需要遍历所有排列，因此时间复杂度与全排列一致。
空间复杂度：O(n)，递归调用栈的深度为 n，且额外使用了长度为 n 的布尔数组 `used`。
该算法通过排序和跳过重复元素有效地避免生成重复的排列。
*/