LeetCode | 0046. Permutations全排列【Python】

LeetCode 0046. Permutations全排列【Medium】【Python】【回溯】【DFS】

Problem

LeetCode

Given a collection of distinct integers, return all possible permutations.

Example:

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

问题

力扣

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

示例:

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

思路

解法一

permutations函数

Python3代码

from itertools import permutations

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # solution one: permutations
        return list(permutations(nums))

解法二

递归

已有的排列放入 path 中，当 nums 为空表示递归完成，再把 path 放入 res 中。

Python3代码

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # solution two: recursion
        res = []
        self.dfs(nums, res, [])
        return res

    def dfs(self, nums, res, path):
        if not nums:
            res.append(path)
        else:
            for i in range(len(nums)):
                self.dfs(nums[:i] + nums[i + 1:], res, path + [nums[i]])

解法三

回溯

visited 数组表示是否访问过这个位置。

Python3代码

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # solution three: backtracking
        visited = [0] * len(nums)
        res = []

        def dfs(path):
            if len(path) == len(nums):
                res.append(path)
            else:
                for i in range(len(nums)):
                    if not visited[i]:
                        visited[i] = 1
                        dfs(path + [nums[i]])
                        visited[i] = 0

        dfs([])
        return res

代码地址

GitHub链接