47. 全排列 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

方法

⭐️ 搜索回溯法

这道题目和46.全排列的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列。
这里又涉及到去重了。
在40.组合总和II 、90.子集II我们分别详细讲解了组合问题和子集问题如何去重。
那么排列问题其实也是一样的套路。
一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。
在46.全排列中已经详解讲解了排列问题的写法，在40.组合总和II 、90.子集II中详细讲解的去重的写法

还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。
我以示例中的 [1,1,2]为例 （为了方便举例，已经排序）抽象为一棵树，去重过程如图：

图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。

重点
一定要画树
1、在哪里会发生重复
2、在回退的时候，哪些变量被撤销了选择。

算法
一、总共26个步骤，18次循环+ 8次回溯

一、先排序
二、递归、回溯
1、如果path, nums长度一样，说明个数选够了

• 将结果加入解集
• return结束当前递归分支

2、循环

• 如果数已经选过了，跳过
• 树层剪枝
• 记录值，值加入path
• 基于当前值继续选，递归
• 回溯，撤销记录

三、返回值

var permuteUnique = function (nums) {
    nums.sort((a, b) => a - b)
    let result = []
    let path = []
    function backtracing(used) {
        if (path.length === nums.length) { // 个数选够了
            result.push(path.slice()) // path的拷贝，加入解集
            return // 结束当前递归分支
        } 
        for (let i = 0; i < nums.length; i++) { // 枚举所有的选择
            if (used[i]) continue; // 这个数使用过了，跳过
            // 剪枝条件，i > 0是为了保证nums[i-1]有意义
            // used[i-1]是因为nums[i-1]在回退的过程中刚刚被撤销选择
            if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) { // 剪枝、去重：!used[i-1]是树层上去重，used[i-1]是树枝上去重，效率还是树层上去重高
                continue
            }
            used[i] = true // 记录路径上做过的选择
            path.push(nums[i]) // make a choice
            backtracing(used) // 基于它继续选，递归
            path.pop() // 回溯，undo the choice
            used[i] = false // 也要撤销一下对它的记录
        }
    }
    backtracing([])
    return result
};

时间复杂度：

• 时间复杂度：O(n×n!），其中 n 为序列的长度。
• 空间复杂度：O(n)。我们需要 O(n) 的标记数组，同时在递归的时候栈深度会达到 O(n)，因此总空间复杂度为 O(n+n)=O(2n)=O(n)。

注意点

• 需要先排序
• 是used[i-1]，而不是used[i]为false时，才能剪枝