- 题目描述
- 思路分析
- 递归中值和引用传递的问题。
- 完整代码
给定一个不含重复数字的数组 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]
使用 used 记录已经使用过的数字， path记录当前结果集合，res记录总的结果。
- 遍历到1，查看1是否使用过，看他是不是在used里面，不在，则加入used，加入当前结果集合path，然后递归调用本函数。
- 又遍历1，看他是否在used里面，显然在，结束本次循环，去遍历第二个数 2。 2不在used里面，所以加入used，加入当前结果集合path，然后递归调用本函数。
- 又遍历1，1在used里，遍历2，2也在used里，遍历3，3不在used里，所以3加入used，加入path。此时显然 path的长度已经等于题目所给的数组长度，则将此时path的答案加入最终答案集合，然后return函数， 开始回溯，将used回退，path回退，
- 这里因为遍历的是3，所以回退之后，当前的 循环也完成了，所以回退过程是 [1,2,3]->[1,2]->[1]，显然下一个遍历的数是3(刚才2已经遍历过了嘛)。这里说的可能比较乱，调试一下程序看看过程就清楚了。
这里有个点需要注意，在我们将path记录到res中的时候，不能直接使用 res.append(path) 可以使用 res.append(path[:])
# 递归的时候变量都保存在栈里，result里面存的是的地址。
但是，当递归函数运行结束，就被pop掉了。
# []是引用 传址调用 引用传递
# [:] 是复制 传值调用
# 在这里 直接append也是空数据 而extend却可以
# 说明append直接是传地址引用，当递归回去的时候引用被释放了，而extend是迭代值再添加属于值的使用。
# 所以 切片也是复制的值传递 类似于 deepcopy？？
完整代码
path = [] # 中间结果集
res = [] # 最终结果集
temp = [] # 已经用过的数字记录
def backtrack(num, temp):
if len(path) == len(num):
# 当前的中间结果已经满足条件 即长度一样了
res.append(path[:])
# res.extend(path)
# res.append(path)
return
for i in range(len(num)):
if num[i] in temp:
continue # 如果当前数字在中间结果集中 表明当前数字已经用过了
path.append(num[i]) # 加入中间结果集
temp.append(num[i]) # 加入已用过数字记录集
backtrack(num, temp)
path.pop()
temp.pop()
backtrack(num, temp)
return res
