题目概要
- 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
知识拓展
- 回溯法（试探法）（穷举法）
- 搜索一个问题的所有解，遍历实现
- 类似枚举的搜索尝试过程
- 走不通就退回再走，此处的退回指的是撤销当前操作，相当于DFS中的状态重置
- 回溯点：满足回溯条件的某个状态点
- 深度优先遍历（DFS）vs 递归 vs 栈
- 三者均为“后进先出”
- 剪枝
- 遍历搜索某一分支时提前知道该分支不能搜到满意结果，就可以提前结束该分支的搜索（预处理工作：排序）
- 重置现场
- 回到完全一样的过去，再开始新的尝试才是有效的
题解概述
本人本次解题用时：1h3min
- 法一：利用标记数组vis。定义递归函数backtrack（first，output），其中first表示从左到右此时填到first处了，output表示当前排列为output。当first==n时，表示填完了，将output放入答案数组，递归结束；当first<n时，考虑first处填哪个数（不能填已经填过的，用标记数组vis来记录），遍历n个数，不在vis就标记并填入，然后继续递归填下一个数，即调用backtrack（first+1，output）。注意，回溯的时候要撤销这一位置填的数以及vis数组中的标记，然后继续尝试其他没被标记过的数
- 法二：去掉标记数组（因为占了空间复杂度）。将n个数的数组nums划分为左右两部分：[0，first-1]（已经填过的数），[first，n-1]（待填的数，用里面i处的数去填first位置的数），从而变成[0，first]（已经填过的数），[first+1，n-1]（待填的数）。注意，回溯的时候交换回来即完成撤销，缺点是答案数组并非按字母序存储
代码记录
//法二（python版）
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
def backtrack(first = 0):
# nums数组已经填完n个数了
if first == n:
res.append(nums[:])
for i in range(first, n):
#动态交换维护数组
nums[first],nums[i] = nums[i], nums[first]
#继续递归去填下一个数，也就是first+1处的数
backtrack(first + 1)
# 撤销操作，回溯的时候再交换回来即完成撤销
nums[first],nums[i] = nums[i], nums[first]
n = len(nums)
res = []
backtrack()
return res
