全排列

46. 全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

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

思路

• 回溯，详情见代码

  # 方法一
  class Solution:
      def permute(self, nums: List[int]) -> List[List[int]]:
          if not nums: return []
          res=[]
          n=len(nums)
          # 使用vis数组保存访问过的元素
          vis=[0]*n
          def backtrack(tmp_list):
              if len(tmp_list)==n:
                  res.append(tmp_list)
              for i in range(n):
                  # 访问过的直接跳过
                  if vis[i]:
                      continue
                  # 状态置为已访问，并将tmp_list加上当前元素继续递归
                  vis[i]=1
                  backtrack(tmp_list+[nums[i]])
                  # 将访问状态初始化，才不会影响别的路径
                  vis[i]=0
          backtrack([])
          return res

# 方法二
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if not nums: return []
        res=[]
        n=len(nums)

        def backtrack2(nums,tmp_list):
            if not nums:
                res.append(tmp_list)
            for i in range(len(nums)):
                # 每次访问过后将i从nums中去除，节省了vis记录访问的空间
                backtrack2(nums[:i]+nums[i+1:],tmp_list+[nums[i]])
        backtrack2(nums,[])
        return res

47. 全排列 II

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

示例:

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

思路：

• 本题和上题的区别在于nums会出现重复元素，这个导致全排列子集需要去重
• 因此本题的难点在于如何去重剪枝

# 方法一、朴素思想
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        if not nums: return []
        res=[]
        def backtrack(nums,tmp_list):
            # 最简单的想法，只需要在tmp_list加入之前判断是否存在于res
            # 但是数组的查找效率为O(N)，因此导致算法整体速度大大下降 
            if not nums and tmp_list not in res:
                res.append(tmp_list)
            for i in range(len(nums)):
                backtrack(nums[:i]+nums[i+1:],tmp_list+[nums[i]])
        backtrack(nums,[])
        return res

# 方法二、记录已访问元素
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        if not nums: return []
        res=[]
        def backtrack(nums,tmp_list):
            # 在递归的开始创建一个空集合
            vis=set()
            if not nums:
                res.append(tmp_list)
            for i in range(len(nums)):
                # 遍历元素的时候，如果该元素在vis中存在，则进行剪枝跳过，否则加入vis
                # 由于set的查找效率为O(1)因此运行速度大大提升
                if nums[i] in vis:
                    continue
                else:
                    vis.add(nums[i])
                backtrack(nums[:i]+nums[i+1:],tmp_list+[nums[i]])
        backtrack(nums,[])
        return res

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： Jason
• 本文链接： https://caicaijason.github.io/2019/11/21/全排列/
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！