Python面试宝典第27题：全排列

见贤思齐

题目        给定一个不含重复数字的数组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、初始化。定义一个空列表用来存储结果。        2、选择。在每一步中，选择一个尚未使用过的数字加入到当前排列中。        3、递归。递归到下一层，继续选择下一个数字。        4、回溯。如果当前排列已经完成（即包含所有数字），则将这个排列添加到结果列表中。否则，撤销本次选择，回溯至上一步，尝试下一个数字。        根据上面的算法步骤，我们可以得出下面的示例代码。defpermutation_by_backtrack(nums):defbacktrack(start=0):ifstart==n:#如果当前排列已经填满，则加入结果集result.append(nums[:])returnforiinrange(start,n):#交换元素以产生新的排列nums[start],nums[i]=nums[i],nums[start]#递归地填充下一个位置backtrack(start+1)#回溯，撤销操作nums[start],nums[i]=nums[i],nums[start]n=len(nums)result=[]backtrack()returnresultprint(permutation_by_backtrack([1,2,3]))print(permutation_by_backtrack([0,1]))print(permutation_by_backtrack([1]))迭代法        迭代法求解本题时，我们可以从空数组开始，逐步增加元素。每次增加一个新元素时，都将这个新元素插入到之前得到的所有排列的每一个可能的位置中。使用回溯法求解本题的主要步骤如下。        1、初始化。创建一个列表，存储当前所有的排列组合，初始为空数组。        2、迭代。对于输入数组中的每一个元素，将这个元素插入到当前所有排列的每一个可能的位置。        3、更新。更新排列组合列表，直到所有元素都被处理完毕。        根据上面的算法步骤，我们可以得出下面的示例代码。defpermutation_by_iteration(nums):results=[[]]fornuminnums:new_results=[]forresultinresults:#将当前元素插入到排列的每一个可能的位置foriinrange(len(result)+1):#复制排列，并在适当位置插入当前元素new_result=list(result)new_result.insert(i,num)new_results.append(new_result)#更新结果列表results=new_resultsreturnresultsprint(permutation_by_iteration([1,2,3]))print(permutation_by_iteration([0,1]))print(permutation_by_iteration([1]))总结        使用回溯法和迭代法求解本题的时间复杂度均为O(N*N!)，这是因为，对于一个长度为N的序列，有N!种排列方式，每一种排列都需要O(N)的时间来构建。回溯法的空间复杂度为O(N)，主要是递归栈的空间消耗，最坏情况下递归的深度为N。迭代法的空间复杂度也为O(N)，此时需要使用额外的数据结构来存储中间状态。        总的来说，回溯法更易于理解和实现，适用于较小规模的问题，但在大规模数据上可能会受到递归深度限制的影响。迭代法在处理大规模数据时表现更好，因为它避免了递归带来的开销，但实现起来稍微复杂一些。💡需要《Python面试宝典》完整源码的大佬们，可订阅专栏后，搜索微信公众号“希望睿智”私信获取。