leetcode hot 100 全排列

46. 全排列

已解答

中等

相关标签

相关企业

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

class Solution(object):

    def permute(self, nums):

        """

        :type nums: List[int]

        :rtype: List[List[int]]

        """

       

        rtrt=[]

        if len(nums)==0:

            return []

        if len(nums)==1:

            return [nums]

        rt = self.permute(nums[1:])

        for sublist in rt:

            for index,sub in enumerate(sublist):

                rtrt.append(sublist[:index]+ [nums[0]] +sublist[index:])

            rtrt.append(sublist+[nums[0]])

        return rtrt

       

两种递归关系

一种是只用n-1的全排列，n可以放到n-1全排列序列的任意一个位置

第二种是 使用n次n-1的全排列，然后遍历一遍数组，每次都把遍历的数组的数放到n-1全排列的的最前面

我们使用方法一

这个最少的世界复杂度都是阶乘，最终返回的结果的数目也是阶乘的级别的