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全排列的的最前面
我们使用方法一
这个最少的世界复杂度都是阶乘，最终返回的结果的数目也是阶乘的级别的