0047._permutations_ii.md

47. Permutations II

难度: Medium

刷题内容

原题连接

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

内容描述

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

解题方案

思路 1 - 时间复杂度: O(N!)- 空间复杂度: O(N)******

跟第46题一样，就是最后append的时候不一样，只有没有结果里面没有的才加入

class Solution:
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) == 0:
            return []
        if len(nums) == 1:
            return [nums]
        res = []
        for i in range(len(nums)):
            prefix = nums[i]
            rest = nums[:i] + nums[i+1:]
            for j in self.permuteUnique(rest):
                if [prefix]+j not in res:
                    res.append([prefix]+j)
        return res