LeetCode-47. 全排列 II【】

@TOC

题目描述：

给定一个可包含重复数字的序列 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. 全排列没有重复数字的序列

解题思路一：回溯

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        self.backtracking(nums, [], [False] * len(nums), res)
        return res

    def backtracking(self, nums, path, used, res):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if (i>0 and nums[i] == nums[i-1] and not used[i-1]) or used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            self.backtracking(nums, path, used, res)
            used[i] = False
            path.pop()

时间复杂度: O(n! * n)
空间复杂度: O(n)
在这里插入图片描述
代码随想录

背诵版

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        self.backtracking(nums, [False] * len(nums), [], res)
        return res

    def backtracking(self, nums, used, path, res):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if (i>0 and nums[i] == nums[i-1] and not used[i-1]) or used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            self.backtracking(nums, used, path, res)
            used[i] = False
            path.pop()