Leetcode 46. 全排列

发表于
| 字数统计: 280 | 阅读时长 ≈ 1

题目描述

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

示例:

1
2
3
4
5
6
7
8
9
10
11
输入: [1,2,3]

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

分析

nums：[1, 2, 3]

  1. 首先将1放入tmp中，此时序列还剩下2，3：
    tmp = [1], nums = [2, 3]
  2. 因为nums中还有剩余，所以再将2放入tmp中 tmp = [1, 2], nums = [3]
  3. 同样，将3放入tmp中：
    tmp = [1, 2, 3], nums = []
    此时tmp中已经没有东西，tmp中是nums的一个全排列。
  4. 之后回到1的情况，此时不将2放入tmp而是将3放入tmp中 tmp = [1, 3], nums = [2]
  5. nums中只剩一个，将其放入tmp中 tmp = [1, 3, 2], nums = []
    [1, 3, 2]也是nums的一个全排列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        def backtrack(nums, tmp):
            # print(nums, tmp)
            if nums == []:
                res.append(tmp)
                return
            for i in range(len(nums)):
                backtrack(nums[:i] + nums[i+1:], tmp + [nums[i]])
        backtrack(nums, [])
        return res

执行用时 :64 ms, 在所有 Python3 提交中击败了91.50%的用户
内存消耗 :13.3 MB, 在所有 Python3 提交中击败了35.97%的用户