47. 全排列 II

https://leetcode-cn.com/problems/permutations-ii/

解法一:回溯

因为有重复数字,所以不能简单用in运算符去重,改用一个布尔数组used,used[i]=True表示该位置已经用过。

回溯之前还应该排序,便于排除重复结果。

此外还需设置一个特殊条件来排除重复结果:used[i] or i-1 >= 0 and nums[i-1] == nums[i] and not used[i-1]

used[i]表示i如果使用了,跳过,很好理解

i-1 >= 0 and nums[i-1] == nums[i] and not used[i-1]表示看前一位,若与当前相等,且前一位未使用过,则跳过。例如对nums=[1,1,1,2],三个1是重复元素,取的时候应该作为一个整体取,即nums的0,1,2号,否则会出现重复结果。上面条件的限制使得nums[1]只有在nums[0]出现的时候才取,同理nums[2]只有在nums[1]出现的时候才取,因此保证了结果中三个1的取用先后次序为nums的0,1,2号。

注意,not used[i-1]也可以改成used[i-1],即前一位使用过,则跳过。还是上面的例子,nums[0]出现后,nums[1]取不了,nums[1]出现后,nums[2]取不了,因此三个1的情况只有是先取nums的2号,然后是1号和0号,和上面反过来

两种思路都可行,都是为了保证相同元素作为一个有序整体取用,从而避免重复

[1,1,1,2]的结果为:

[[1,1,1,2],[1,1,2,1],[1,2,1,1],[2,1,1,1]]

可以看出第0和第3组以三个1为整体,第1第2组分别以前两个1和后两个1为整体

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        tmpList = []
        used = [False] * len(nums)    #标记数组
        nums.sort()
        self.backtrack(nums, tmpList, used)
        return self.res
    
    def backtrack(self, nums, tmpList, used):
        if len(tmpList) == len(nums):
            self.res.append(list(tmpList))
        for i in range(len(nums)):
            #注意复杂条件,最后一个可改为used[i-1]
            if used[i] or i-1 >= 0 and nums[i-1] == nums[i] and not used[i-1]:
                continue
            used[i] = True
            self.backtrack(nums, tmpList + [nums[i]], used)
            used[i] = False    #还原现场

另一种思路:

若重复数字1,1,1中有一个(如第二个)被使用了,则下次选择不选第二个1前面的1,只能往后选:

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dfs(tmp, used):
            if len(tmp) == n:
                res.append(list(tmp))
            else:
                for i in range(n):
                    if used[i]:    #使用过则跳过
                        continue
                    else:    #若未使用过,看i右边是否有相等且使用过的数字
                        j = i
                        while j+1 < n and used[j] == False and nums[j] == nums[j+1]:
                            j += 1
                        if used[j]:    #若有则跳过
                            continue
                    used[i] = True
                    dfs(tmp + [nums[i]], used)
                    used[i] = False
                    
        nums.sort()
        n = len(nums)
        used = [False] * n
        res = []
        dfs([], used)
        return res

最后更新于