给定一个没有重复数字的序列，返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
class Solution: def permute(self, nums: List[int]) -> List[List[int]]: def backtrack(first = 0): # if all integers are used up if first == n: output.append(nums[:]) for i in range(first, n): # place i-th integer first # in the current permutation nums[first], nums[i] = nums[i], nums[first] # use next integers to complete the permutations backtrack(first + 1) # backtrack nums[first], nums[i] = nums[i], nums[first] n = len(nums) output = [] backtrack() return output回溯算法 回溯法（back tracking）（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 解题的一般步骤是： 1.定义一个解空间，它包含问题的解； 2.利用适于搜索的方法组织解空间； 3.利用深度优先法搜索解空间； 4.利用限界函数避免移动到不可能产生解的子空间。
