【Day 82 】2024-11-04 - 47 全排列 II

[azl397985856]

47 全排列 II

入选理由

暂无

题目地址

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

前置知识

• 回溯
• 数组
• 剪枝

  题目描述

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

示例:

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

[Fightforcoding]

class Solution: # T: O(n n!) S: O(n n!) def permuteUnique(self, nums: List[int]) -> List[List[int]]:

    nums.sort()
    res = []
    def backtrack(pre, arr):
        if len(arr) == 1:
            res.append(pre + arr)
            return             
        for i in range(len(arr)):
            if i - 1 >= 0 and arr[i] == arr[i-1]:
                continue

            backtrack(pre+[arr[i]], arr[:i]+arr[i+1:])

    backtrack([], nums)
    return res

[qiaoeve]

''' class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: def dfs(x): if x == len(nums) - 1: res.append(list(nums)) # 添加排列方案 return dic = set() for i in range(x, len(nums)): if nums[i] in dic: continue # 重复，因此剪枝 dic.add(nums[i]) nums[i], nums[x] = nums[x], nums[i] # 交换，将 nums[i] 固定在第 x 位 dfs(x + 1) # 开启固定第 x + 1 位元素 nums[i], nums[x] = nums[x], nums[i] # 恢复交换 res = [] dfs(0) return res ''' 时间复杂度：O(N！N)

[huizsh]

class Solution: def backtrack(numbers, pre): nonlocal res if len(numbers) <= 1: res.append(pre + numbers) return for key, value in enumerate(numbers): if value not in numbers[:key]: backtrack(numbers[:key] + numbers[key + 1:], pre+[value])

res = []
if not len(nums): return []
backtrack(nums, [])
return res