给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入:
[1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
废话不多说，直接上回溯算法框架。解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
回溯算法的框架如下：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。
下面说一下回溯搜索的思想：
1、什么是“树形问题”？为什么为什么是在树形问题上使用“深度优先遍历”？不用深度优先遍历我们还可以用什么？
2、什么是“回溯”？为什么需要回溯？
3、不回溯可以吗？
首先介绍“回溯”算法的应用。“回溯”算法也叫“回溯搜索”算法，主要用于在一个庞大的空间里搜索我们所需要的问题的解。我们每天使用的“搜索引擎”就是帮助我们在庞大的互联网上搜索我们需要的信息。“搜索”引擎的“搜索”和“回溯搜索”算法的“搜索”意思是一样的。
“回溯”指的是“状态重置”，可以理解为“回到过去”、“恢复现场”，是在编码的过程中，是为了节约空间而使用的一种技巧。而回溯其实是“深度优先遍历”特有的一种现象。之所以是“深度优先遍历”，是因为我们要解决的问题通常是在一棵树上完成的，在这棵树上搜索需要的答案，一般使用深度优先遍历。
“全排列”就是一个非常经典的“回溯”算法的应用。我们知道，N 个数字的全排列一共有 N!这么多个。
大家可以尝试一下在纸上写 3 个数字、4 个数字、5 个数字的全排列，相信不难找到这样的方法。
以数组 [1, 2, 3] 的全排列为例。
我们先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]；
再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]；
最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]。
我们只需要按顺序枚举每一位可能出现的情况，已经选择的数字在接下来要确定的数字中不能出现。按照这种策略选取就能够做到不重不漏，把可能的全排列都枚举出来。
在枚举第一位的时候，有 3 种情况。
在枚举第二位的时候java全排列算法，前面已经出现过的数字就不能再被选取了；
在枚举第三位的时候，前面 2 个已经选择过的数字就不能再被选取了。
这样的思路，我们可以用一个树形结构表示。看到这里的朋友，建议自己先尝试画一下“全排列”问题的树形结构。
使用编程的方法得到全排列，就是在这样的一个树形结构中进行编程，具体来说，就是执行一次深度优先遍历，从树的根结点到叶子结点形成的路径就是一个全排列。
说明：
1、每一个结点表示了“全排列”问题求解的不同阶段，这些阶段通过变量的“不同的值”体现；
2、这些变量的不同的值，也称之为“状态”；
3、使用深度优先遍历有“回头”的过程，在“回头”以后，状态变量需要设置成为和先前一样；
4、因此在回到上一层结点的过程中，需要撤销上一次选择，这个操作也称之为“状态重置”；
5、深度优先遍历，可以直接借助系统栈空间，为我们保存所需要的状态变量java全排列算法-给定一个 没有重复 数字的序列，返回其所有可能的全排列。，在编码中只需要注意遍历到相应的结点的时候，状态变量的值是正确的，具体的做法是：往下走一层的时候，path 变量在尾部追加，而往回走的时候，需要撤销上一次的选择，也是在尾部操作，因此 path 变量是一个栈。
6、深度优先遍历通过“回溯”操作，实现了全局使用一份状态变量的效果。
下面我们解释如何编码：
1、首先这棵树除了根结点和叶子结点以外，每一个结点做的事情其实是一样的，即在已经选了一些数的前提，我们需要在剩下还没有选择的数中按照顺序依次选择一个数，这显然是一个递归结构；
2、递归的终止条件是，数已经选够了，因此我们需要一个变量来表示当前递归到第几层，我们把这个变量叫做 depth；
3、这些结点实际上表示了搜索（查找）全排列问题的不同阶段，为了区分这些不同阶段，我们就需要一些变量来记录为了得到一个全排列，程序进行到哪一步了，在这里我们需要两个变量：
（1）已经选了哪些数，到叶子结点时候，这些已经选择的数就构成了一个全排列；
（2）一个布尔数组 used，初始化的时候都为 false 表示这些数还没有被选择，当我们选定一个数的时候，就将这个数组的相应位置设置为 true ，这样在考虑下一个位置的时候，就能够以 O(1)的时间复杂度判断这个数是否被选择过，这是一种“以空间换时间”的思想。
我们把这两个变量称之为“状态变量”，它们表示了我们在求解一个问题的时候所处的阶段。
4、在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。
5、另外，因为是执行深度优先遍历，从较深层的结点返回到较浅层结点的时候，需要做“状态重置”，即“回到过去”、“恢复现场”，我们举一个例子。
从 [1, 2, 3] 到 [1, 3, 2] ，深度优先遍历是这样做的，从 [1, 2, 3] 回到 [1, 2] 的时候，需要撤销刚刚已经选择的数 3，因为在这一层只有一个数 3 我们已经尝试过了，因此程序回到上一层，需要撤销对 2 的选择，好让后面的程序知道，选择 3 了以后还能够选择 2。
这种在遍历的过程中，从深层结点回到浅层结点的过程中所做的操作就叫“回溯”。
java（有错，可以想想哪里错了）
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List permute(int[] nums) {
// 首先是特判
int len = nums.length;
// 使用一个动态数组保存所有可能的全排列
List res = new ArrayList();
if (len == 0) {
return res;
}
boolean[] used = new boolean[len];
List path = new ArrayList();
dfs(nums, len, 0, path, used, res);
return res;
}
private void dfs(int[] nums, int len, int depth,
List path, boolean[] used,
List res) {
if (depth == len) {
res.add(path);
return;
}
for (int i = 0; i List[List[int]]:
def dfs(nums, size, depth, path, used, res):
if depth == size:
res.append(path)
return
for i in range(size):
if not used[i]:
used[i] = True
path.append(nums[i])
dfs(nums, size, depth + 1, path, used, res)
used[i] = False
path.pop()
size = len(nums)
if len(nums) == 0:
return []
used = [False for _ in range(size)]
res = []
dfs(nums, size, 0, [], used, res)
return res
if __name__ == '__main__':
nums = [1, 2, 3]
solution = Solution()
res = solution.permute(nums)
print(res)
运行时输出如下：
[[], [], [], [], [], []]
为什么呢？一一步一步debug，原来递归的终止条件在这里：
if (depth == len) {
res.add(path);
return;
}
path 这个变量所指向的对象在递归的过程中只有一份，深度优先遍历完成以后，因为回到了根结点（因为我们之前说了，从深层结点回到浅层结点的时候，需要撤销之前的选择），因此 path 这个变量回到根结点以后都为空。
在 Java 中，因为都是值传递，对象类型变量在传参的过程中，复制的都是变量的地址。（ 我不是很清楚 中方法变量的传递机制，所以暂时没有写，欢迎知道的朋友补充，但是从实验的结果上看和 Java 很像。）这些地址被添加到 res 变量，但实际上指向的是同一块内存地址，因此我们会看到 6 个空的列表对象。解决的方法很简单，在 res.add(path); 这里做一次拷贝即可。
修改的部分：
java
if (depth == len) {
res.add(new ArrayList(path));
return;
}
if depth == size:
res.append(path[:])
return
写 回溯 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。
其实想想看，回溯算法和动态规划是不是有点像呢？我们在动态规划系列文章中多次强调，动态规划的三个需要明确的点就是「状态」「选择」和「base case」，是不是就对应着走过的「路径」，当前的「选择列表」和「结束条件」？
某种程度上说，动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用 dp table 或者备忘录优化java全排列算法，将递归树大幅剪枝，这就变成了动态规划。而今天的两个问题，都没有重叠子问题，也就是回溯算法问题了，复杂度非常高是不可避免的。
不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！
以上参考：
链接：
文章来源:https://blog.csdn.net/weixin_45333934/article/details/105744849