0047：全排列 II（★）

2015-02-16 约 218 字预计阅读 1 分钟次阅读

力扣第 47 题

题目

给定一个可包含重复数字的序列 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

分析

0046 升级版，用计数器标记还未选的数即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dfs():
            if len(path) == len(nums):
                res.append(path[:])
                return
            for x in ct:
                if ct[x]:
                    ct[x]-=1
                    path.append(x)
                    dfs()
                    path.pop()
                    ct[x]+=1

        ct = Counter(nums)  
        res, path = [], []
        dfs()
        return res

49 ms

目录

0047：全排列 II（★）

题目

分析

解答