0047. 全排列 II #

标签：数组、回溯
难度：中等

题目大意 #

描述：给定一个可包含重复数字的序列 nums。

要求：按任意顺序返回所有不重复的全排列。

说明：

$1 \le nums.length \le 8$。
$-10 \le nums[i] \le 10$。

示例：

示例 1：

1
2


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

示例 2：

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：回溯算法 #

这道题跟「 0046. 全排列」不一样的地方在于增加了序列中的元素可重复这一条件。这就涉及到了如何去重。

我们可以先对数组 nums 进行排序，然后使用一个数组 visited 标记该元素在当前排列中是否被访问过。

如果未被访问过则将其加入排列中，并在访问后将该元素变为未访问状态。

然后再递归遍历下一层元素之前，增加一句语句进行判重：if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]: continue。

然后再进行回溯遍历。

思路 1：代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution:
    res = []
    path = []
    def backtrack(self, nums: List[int], visited: List[bool]):
        if len(self.path) == len(nums):
            self.res.append(self.path[:])
            return
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]:
                continue

            if not visited[i]:
                visited[i] = True
                self.path.append(nums[i])
                self.backtrack(nums, visited)
                self.path.pop()
                visited[i] = False

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        self.res.clear()
        self.path.clear()
        nums.sort()
        visited = [False for _ in range(len(nums))]
        self.backtrack(nums, visited)
        return self.res

思路 1：复杂度分析 #

时间复杂度：$O(n \times n!)$，其中 $n$ 为数组 nums 的元素个数。
空间复杂度：$O(n)$。