0046：全排列（★）

2015-02-15 约 296 字预计阅读 1 分钟次阅读

力扣第 46 题

题目

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

分析

#1

python 里可以直接调库。

1
2
3


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

37 ms

#2

还可以用回溯法，依次选择数字，注意标记选过的数字。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs():
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i, x in enumerate(nums):
                if x<inf:
                    nums[i]=inf
                    path.append(x)
                    dfs()
                    path.pop()
                    nums[i]=x
                    
        res, path = [], []
        dfs()
        return res

40 ms

目录

0046：全排列（★）

题目

分析

#1

#2

解答