专栏首页Petrichor的专栏leetcode: 47. Permutations II

leetcode: 47. Permutations II

Problem

# Given a collection of numbers that might contain duplicates, 
# return all possible unique permutations.
# 
# For example,
# [1,1,2] have the following unique permutations:
# [1,1,2], [1,2,1], and [2,1,1].

AC

# DFS
class Solution():
    def permuteUnique(self, x):
        return self.dfs(x)
    def dfs(self, x):
        if len(x) == 0:
            return []
        if len(x) == 1:
            return [x]
        pre, cur = self.dfs(x[:-1]), []
        for p in pre:
            for i in range(len(x)):
                if p[:i] + [x[-1]] + p[i:] not in cur:  # 加上一句去重
                    cur.append(p[:i] + [x[-1]] + p[i:])
        return cur


if __name__ == "__main__":
    assert Solution().permuteUnique([1, 1, 2]) == [[2, 1, 1], [1, 2, 1], [1, 1, 2]]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode: 80. Remove Duplicates from Sorted Array II

    leetcode: 26. Remove Duplicates from Sorted Array

    JNingWei
  • leetcode: 46. Permutations

    JNingWei
  • leetcode: 70. Climbing Stairs

    JNingWei
  • python pyqt5 QMessageBox 消息框

    import sys from PyQt5.QtCore import * from PyQt5.QtGui import * from PyQt5.Qt...

    用户5760343
  • Python求解一元二次方程根

    本文使用Python实现一元二次方程求根公式,主要演示运算符和几个内置函数的用法,封面图片与本文内容无关。 def root(a, b, c, highmidd...

    Python小屋屋主
  • [牛客OI测试赛2]F假的数学游戏(斯特灵公式)

    $n! \approx \sqrt{2 \pi n} (\frac{n}{e})^n$

    attack
  • Python在计算内存时值得注意的几个问题

    我之前的一篇文章,带大家揭晓了 Python 在给内置对象分配内存时的 5 个奇怪而有趣的小秘密。文中使用了sys.getsizeof()来计算内存,但是用这个...

    AI科技大本营
  • LeetCode - 删除最外层的括号

    原题地址:https://leetcode-cn.com/problems/remove-outermost-parentheses/

    晓痴
  • python 写window服务

    import win32serviceutil import win32service import win32event import os impo...

    用户5760343
  • 【leetcode刷题】T175-判断子序列

    你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。

    木又AI帮

扫码关注云+社区

领取腾讯云代金券