全排列II

47. 全排列 II - 力扣（LeetCode）

问题简述

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

思路

• 递归回溯的关键问题是，在生成递归树的过程中，每个节点应该生成哪些分支；

• 相比无重复的全排列，需要额外考虑一个去重的剪枝过程，这里提供了写法1 和写法2 两种剪枝方法；

  • 写法 1 是最常见的写法，解释成本低；

  • 如果画出递归树的生成过程，那么写法2 更直观的；

Python 写法1（推荐）

• 本写法中核心的去重剪枝有两种写法：

  # 写法1（推荐）
  if i > 0 and nums[i] == nums[i - 1] and not used[i - i]:
      continue
  
  # 写法2，区别仅在于 used[i - i]
  if i > 0 and nums[i] == nums[i - 1] and used[i - i]:
      continue

  写法1 的效率更高，关于这两种写法的实际含义，详见：47. 全排列 II - 「代码随想录」

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        
        nums.sort()  # 先排序，剪枝需要
        len_nums = len(nums)
        ret = []
        used = [0] * len_nums

        def dfs(deep, tmp):
            if deep == len_nums:
                ret.append(tmp[:])
                return
            
            for i in range(len_nums):
                if used[i]: continue
                # 相比无重复的全排列，多了这一步剪枝过程，该剪枝过程依赖于 nums 有序
                if i > 0 and nums[i] == nums[i - 1] and not used[i - i]:
                    continue
                
                used[i] = 1
                tmp.append(nums[i])
                dfs(deep + 1, tmp)
                tmp.pop()
                used[i] = 0
        
        dfs(0, [])
        return ret

Python 写法2（直观）

• 在递归树的每一层中，维护一个集合，记录已经使用过的数字；

• 该方法不需要预先排序；

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        
        # nums.sort()  # 先排序，剪枝需要
        len_nums = len(nums)
        ret = []
        used = [0] * len_nums

        def dfs(deep, tmp):
            if deep == len_nums:
                ret.append(tmp[:])
                return
            
            book = set()  # 该变量在递归树的每一层共享，记录在这一层中已经用过了哪些数字
            for i in range(len_nums):
                if used[i] or nums[i] in book: continue
                book.add(nums[i])
                
                used[i] = 1
                tmp.append(nums[i])
                dfs(deep + 1, tmp)
                tmp.pop()
                used[i] = 0
        
        dfs(0, [])
        return ret

相关问题

• 46. 全排列 - 力扣（LeetCode）