刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/permutations-ii/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

思路

任意顺序的话，基底思路用回溯法遍历全树即可，当然，比较重要的点就在剪枝思路了：

• 只返回不重复全排列，所以可以有一个重复元素剪枝
• 可能存在重复数字，所以剪枝时需要注意可能存在多个元素

还有一个比较基础但是很重要的思维就是，既然可能存在重复元素，那么开始之前先做一次排序，会更容易筛选出重复元素的情况，并加以限制，便于逻辑编写

具体可以参考官方题解

代码

func permuteUnique(nums []int) (ans [][]int) {
    sort.Ints(nums)
    n := len(nums)
    tempAns := []int{}
    hasUsed := make([]bool, n)
    var backtrack func(int)
    backtrack = func(idx int) {
        if idx == n {
            temp := make([]int, 0)
            ans = append(ans, append(temp, tempAns...))
            return
        }
        for i, v := range nums {
            if hasUsed[i] || i > 0 && !hasUsed[i-1] && v == nums[i-1] {
                continue
            }
            tempAns = append(tempAns, v)
            hasUsed[i] = true
            backtrack(idx + 1)
            hasUsed[i] = false
            tempAns = tempAns[:len(tempAns)-1]
        }
    }
    backtrack(0)
    return
}