0047. 全排列 II

0047. 全排列 II #

  • 标签:数组、回溯
  • 难度:中等

题目大意 #

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

解题思路 #

这道题跟「 0046. 全排列」不一样的地方在于增加了序列中的元素可重复这一条件。这就涉及到了去重。先对 nums 进行排序,然后使用 visited 数组标记该元素在当前排列中是否被访问过。若未被访问过则将其加入排列中,并在访问后将该元素变为未访问状态。

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

然后进行回溯遍历。

代码 #

 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
本站总访问量  次  |  您是本站第  位访问者