47. 全排列 II

Difficulty
Medium
Tags
回溯
URL
https://leetcode-cn.com/problems/permutations-ii/
Star
给定一个可包含重复数字的序列 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

法1 回溯

思路
本体数组包含重复数字，且是排列题目。所以每次加到path中时，既要判断相同的值同一层之前（之前已经走完的路径）有没有使用过，使用过就不行了，还要判断之前层（即当前走的路径）有没有使用过该元素（此时不管该元素是否为重复值），如果使用过也是不行的。
所以最朴素的做法就是采用两个bool数组来记录走过的元素：
  • 一个bool数组用来记录当前路径上走过的元素（注意，如果没有重复元素的话没事可以通过if nums[i] in path 来判断某元素有无在当前路径上，但是有重复元素，所以需要借助一个bool数组）。这个其实是记录当前的下标有没有使用过。由于该bool数组会随着遍历的深度不断改变，所以需要作为参数不断的改变。
  • 一个bool数组用来记录当前层上相同的元素有没有被遍历过。对同一层而言，如果有相同的元素参与过深度遍历了，那么就没必要再参与一次了。由于该bool数组只判断当前层，所以需要在层内初始化，且每层都会初始化一次。
该朴素的代码实现如题解所示。
注：判断同层相同的元素有无使用过不能使用bool数组，而应该使用hashMap或者set，因为bool只能记录某个特定的值有没有使用过，而不能记录相同的多个值中某一个有没有使用过。我们这里的目的是判断相同的元素有没有使用过。
同层值相同的元素不能重复用，所以采用hashMap 或者set来记录 路径上是 位置相同的元素不能重复使用。判断位置是否相同，直接用bool数组记录即可
 
进阶理解，可以把两个bool数组合并起来。判断层间的bool数组肯定没法判断当前路径上的元素使用情况。但是判断当前路径上元素的使用情况是否可以同时用来判断当前层元素的使用情况呢？
答案是可以的，见改进版题解代码。
 
如果觉得进阶版本不好理解，使用两个bool数组也是完全可以的
notion imagenotion image
题解
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        self.res = []
        visited = [False for _ in nums]
        self.dfs(path=[], nums=nums, visited=visited)
        return self.res


    def dfs(self, path, nums, visited):
        if len(path) == len(nums):
            self.res.append(path[:])
            return

        used = set()
        for i in range(0, len(nums)):
            # 同层的 值相同的元素 不能重复使用
            if nums[i] in used:
                continue
            # 一条路径上的元素，相同下标的不能重复使用
            if visited[i]:
                continue
            used.add(nums[i])
            
            visited[i] = True
            path.append(nums[i])
            self.dfs(path, nums, visited)
            path.pop()
            visited[i] = False


# ------------------------改进版---------------------#
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        nums.sort()
        visited = [0 for _ in range(len(nums))]
        self.dfs(path=[], nums=nums, visited=visited)
        return self.res

    def dfs(self, path, nums, visited):
        if len(path) == len(nums):
            self.res.append(path[:])

        for i in range(len(nums)):
						# 在当前路径上使用过。如果没有重复元素可以直接 if nums[i] in path 来判断
            if visited[i] == 0:
								# 相同的元素在本层之前使用过，是使用过且已经结束回溯了
                # 所以visited[i-1]又恢复到了0。
								# 因为遍历是从前向后遍历的，所以当visited[i-1] == 0时，说明肯定是走完一次回溯了
								# 那什么时候 visited[i-1] == 1 呢，是只有当nums[i-1]正在当前path中的时候。
                if i > 0 and nums[i] == nums[i-1] and visited[i-1] == 0:
                    continue
                visited[i] = 1
                path.append(nums[i])
                self.dfs(path, nums, visited)
                visited[i] = 0
                path.pop()
感觉改进版反而不好理解了。。。