47、全排列 II

题目

给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

答案1

答案是正确的但是超出时间限制，是str方法的原因吧

#
# @lc app=leetcode.cn id=47 lang=python3
#
# [47] 全排列 II
#

# @lc code=start
from typing import List


class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:

        res = []
        tempL = []
        flagL = [False for x in range(len(nums))]

        def helper(index):
            if index == len(nums) - 1:
                if str(tempL[:]) not in str(res):
                    res.append(tempL[:])
                return
            for i in range(len(nums)):
                if not flagL[i]:
                    tempL.append(nums[i])
                    flagL[i] = True
                    helper(index + 1)
                    flagL[i] = False
                    tempL.pop()

        helper(-1)
        return res


l = [1, 1, 2]
Solution().permuteUnique(l)
# @lc code=end

答案2

#
# @lc app=leetcode.cn id=47 lang=python3
#
# [47] 全排列 II
#

# @lc code=start
from typing import List


class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:

        res = []
        tempL = []
        flagL = [False for x in range(len(nums))]

        def helper(index):
            if index == len(nums) - 1:
                res.append(tempL[:])
                return
            for i in range(len(nums)):
                if not flagL[i]:
                    tempL.append(nums[i])
                    flagL[i] = True
                    helper(index + 1)
                    flagL[i] = False
                    tempL.pop()

        helper(-1)
        realRes = []
        for i in res:
            if i not in realRes:
                realRes.append(i)
        return realRes



# @lc code=end

勉强通过

Note

dfs+回溯的问题
去重问题还再考虑