给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [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):
n = len(nums)
def backtrack(first=0):
# 如果所有的数字都被使用了
if first == n:
output.append(nums[:])
for i in range(first, n):
# 把第i个数字放在最前面
nums[first], nums[i] = nums[i], nums[first]
# 再对之后的数字进行全排列
backtrack(first+1)
# 回溯(退回上一步状态)
nums[first], nums[i] = nums[i], nums[first]
output = []
backtrack()
return output
