LeetCode-46 全排列

发表于 | 分类于 | 评论数： | 阅读次数：

题目：全排列

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

示例:

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

思路

这题需要用到递归的思想：

  • 当只有两个数时，依次将数字取出放到最后即可。

  • 当有多余两个数时，依次将第i个数取出，放置到剩余部分的最后，剩余部分看做一个整体（即nums[:i] + nums[i + 1:]）。

  • 对剩余部分进行递归即可。

实现：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        out = []
        if len(nums) == 1:
            return [nums]
        for index, item in enumerate(nums):
            res = nums[:index] + nums[index + 1:] 
            for j in self.permute(res): 
                out.append(j + [item])
        return out

其他思考

其实Python的itertools库中提供了内置的全排列方法:

1
2
3
4
5
6
7
8
class permutations(object):
    """
    permutations(iterable[, r]) --> permutations object
    
    Return successive r-length permutations of elements in the iterable.
    
    permutations(range(3), 2) --> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1)
    """

现实中可以直接调用：

1
2
3
4
5
6
7
class Solution:
    def permute(self, nums):
        import itertools
        out = []
        for i in itertools.permutations(nums, len(nums)):
            out.append(i)
        return out

如果大家有更好的方法，欢迎一起探讨。