leetcode 47. 全排列 II

目录

1. 解题思路
2. 代码

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

解题思路

cnts 是每个数字出现的次数
每次使用一个数字都尝试使用 1 个、2 个 … 到用完这个数字。除此之外，不允许有两次连续选择相同数字

代码

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        import collections
        n = len(nums)
        cnts = collections.Counter(nums)
        nums = list(cnts.keys())
        l = [0] * n
        ans = []
        def dfs(i):
            if i == n:
                ans.append(l[::])
                return
            for num in nums:
                if i > 0 and l[i-1] == num: continue
                oc = cnts[num]
                if oc > 0:
                    j = 0
                    while cnts[num] > 0:
                        cnts[num] -= 1
                        l[i + j] = num
                        dfs(i+j+1)
                        j += 1
                    cnts[num] = oc
        dfs(0)
        return ans