47. 全排列 II

[Geekhyt]

原题链接

回溯

本题与 46. 全排列解题思路一样。

不同之处：序列 nums 是可以重复的，要求按任意顺序返回所有不重复的全排列。

1. 去重就要排序，排序后可以使相同的数字相邻，便于去重。
2. 使用 used 数组记录使用过的数字，true 代表使用过，false 代表未使用过。
3. 在迭代的过程中需要考虑好情况，充分剪枝。
4. 在选择时记录 used[i] 状态，撤销时也要重置 used[i] 状态。

const permuteUnique = function(nums) {
    const len = nums.length, res = [], used = []
    nums.sort((a, b) => a - b)
    const backtrack = (deepStack) => {
        if (deepStack.length === len) {
            res.push(deepStack.slice())
            return
        }
        for (let i = 0; i < len; i++) {
            // 当前选项与上一项相同、且上一项存在、且没有被使用过，则忽略
            if (nums[i - 1] === nums[i] && i - 1 >= 0 && !used[i - 1]) continue 
            if (used[i]) continue // 使用过便不再使用
            deepStack.push(nums[i])
            used[i] = true
            backtrack(deepStack)
            deepStack.pop()
            used[i] = false
        }
    }
    backtrack([])
    return res
}

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