题目

        给定一个不含重复数字的数组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、回溯。如果当前排列已经完成（即包含所有数字），则将这个排列添加到结果列表中。否则，撤销本次选择，回溯至上一步，尝试下一个数字。

        根据上面的算法步骤，我们可以得出下面的示例代码。

def permutation_by_backtrack(nums):def backtrack(start = 0):if start == n:# 如果当前排列已经填满，则加入结果集result.append(nums[:])returnfor i in range(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()return resultprint(permutation_by_backtrack([1, 2, 3]))
print(permutation_by_backtrack([0, 1]))
print(permutation_by_backtrack([1]))

迭代法

        迭代法求解本题时，我们可以从空数组开始，逐步增加元素。每次增加一个新元素时，都将这个新元素插入到之前得到的所有排列的每一个可能的位置中。使用回溯法求解本题的主要步骤如下。

        1、初始化。创建一个列表，存储当前所有的排列组合，初始为空数组。

        2、迭代。对于输入数组中的每一个元素，将这个元素插入到当前所有排列的每一个可能的位置。

        3、更新。更新排列组合列表，直到所有元素都被处理完毕。

        根据上面的算法步骤，我们可以得出下面的示例代码。

def permutation_by_iteration(nums):results = [[]]for num in nums:new_results = []for result in results:# 将当前元素插入到排列的每一个可能的位置for i in range(len(result) + 1):# 复制排列，并在适当位置插入当前元素new_result = list(result)new_result.insert(i, num)new_results.append(new_result)# 更新结果列表results = new_resultsreturn resultsprint(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)，此时需要使用额外的数据结构来存储中间状态。

        总的来说，回溯法更易于理解和实现，适用于较小规模的问题，但在大规模数据上可能会受到递归深度限制的影响。迭代法在处理大规模数据时表现更好，因为它避免了递归带来的开销，但实现起来稍微复杂一些。