天天刷leetcode——46.全排列

全排列

地址: https://leetcode-cn.com/problems/permutations/.

题目描述

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

解题思路

1. 回溯算法

回溯的核心就是一个多叉树的遍历过程。只需要从根遍历这个树，记录路上的数，所有路径就是全排列。

回溯算法的核心架构：

def traveser(track, choiceList):
    '''
    :param track: 路径
    :param choiceList: 选择列表
    :return: res
    '''
    # if 满足结束条件：
    #     result.append(track)
    #     return 
    for i in range(len(choiceList)):
        # 排除不合法的操作
        # 做选择
        traveser(track,choiceList) # 进入下一层决策树
        track.pop(-1)   # c撤销选择

本题的代码：

    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(nums,track):
            # 结束条件，nums的长度等于track长度
            if len(track) == len(nums):
                res.append(track[:])
                return 
            for i in range(len(nums)):
                # 排除不合法的选择
                if nums[i] in track:
                    continue
                # 做选择
                track.append(nums[i])
                # 进入下一层决策树
                backtrack(nums,track)
                #  取消选择
                track.pop(-1)

        # 路径记录在track
        # 选择列表：nums不存在与track中的那些元素
        # 结束条件：nums中的元素都在track中出现
        res = []
        track =[]
        backtrack(nums,track)
        return res

之间

if len(track) == len(nums):
   res.append(track)
   return 

结果却是[[],[],[],[],[],[]],看了leetcode上有人的解释：track变量所指向的对象在递归的过程中只有一份，深度优先遍历完成之后，因为回到了根节点，因此track这个变量回到根节点以后都是空。python中方法变量的传递为值传递，这些地址被添加到res变量，单实际上指向的上同一块内存地址，因此每次都是空列表对象。这个时候，只需要把track换成track[:]，做一次值拷贝就行了
总结：空间复杂度全排列个数为N！每个全排列占空间N就是O(NN!)。时间复杂度O(NN!)

2. 直接递归

递归结束条件：当列表内只有一个元素，全排列就是自己
递归过程：以取一个数，然后递归其他数的方式求出所有的全排列。
比如：
[1,3,4,4,5,6]取[1],然后全排列[3,4,5,6]。

def permute(self,nums:List[int]):
	if len(nums) <= 1:
		return [nums]
	res = []
	for idx,num in enumerate(nums):
		res_num = nums[:idx] + nums[idx+1:]
		for j in self.permuate(res_nums):
			res.append([num]+j)
	return res

references

[1] leetcode 46 全排列: https://leetcode-cn.com/problems/permutations/submissions/

本文地址：https://blog.csdn.net/qq_30516823/article/details/107659523