目录
- 问题分析使用什么方法？什么是回溯法？怎么使用回溯法？回溯法的具体实施回溯法的延伸
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
Copy输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
问题分析#
使用什么方法？#
全排列很明显使用回溯法来进行解答
什么是回溯法？#
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
怎么使用回溯法？#
运用回溯法解题的关键要素有以下三点：
- 针对给定的问题，定义问题的解空间；
- 确定易于搜索的解空间结构；
- 以深度优先方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。什么是深度优先搜索？#深度优先搜索（缩写DFS）有点类似广度优先搜索，也是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。
代码模板是什么样子的？#
Copyvoid BackTrace(int t) {
if(t>n)
Output(x);
else
for(int i = f (n, t); i <= g (n, t); i ) {
x[t] = h(i);
if(Constraint(t) && Bound (t))
BackTrace(t 1);
}
}
其中，t表示递归深度，即当前扩展结点在解空间树中的深度；n用来控制递归深度，即解空间树的高度。当t>n时，算法已搜索到一个叶子结点，此时由函数Output(x)对得到的可行解x进行记录或输出处理
用 f(n, t)和 g(n, t)分别表示在当前扩展结点处未搜索过的子树的起始编号和终止编号；h(i)表示在当前扩展结点处x[t]的第i个可选值；函数Constraint(t)和 Bound(t)分别表示当前扩展结点处的约束函数和限界函数。若函数Constraint(t)的返回值为真，则表示当前扩展结点处x[1:t]的取值满足问题的约束条件；否则不满足问题的约束条件。若函数Bound(t)的返回值为真，则表示在当前扩展结点处x[1:t]的取值尚未使目标函数越界，还需由BackTrace(t 1)对其相应的子树做进一步地搜索；否则，在当前扩展结点处x[1:t]的取值已使目标函数越界，可剪去相应的子树。
回溯法的具体实施#
Copyclass Solution {
public List<List<Integer>> permute(int[] nums) {
//LeetCode代码模板
}
}
step 1 定义问题的解空间#
什么是解空间？
应用回溯法求解问题时，首先应明确定义问题的解空间，该解空间应至少包含问题的一个最优解。例如，对于有n种物品的 0-1 背包问题，其解空间由长度为n的 0-1 向量组成，该解空间包含了对变量的所有可能的0-1 赋值。当n=3时，其解空间是{ (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) }
在定义了问题的解空间后，还需要将解空间有效地组织起来，使得回溯法能方便地搜索整个解空间，通常将解空间组织成树或图的形式。例如，对于n= 3的0-1 背包问题，其解空间可以用一棵完全二叉树表示，从树根到叶子结点的任意一条路径可表示解空间中的一个元素，如从根结点A到结点J的路径对应于解空间中的一个元素(1, 0, 1)。
定义本题的解空间
全排列问题，因为输入数组的长度为n = nums.length，解空间就是一个森林：
这里需要一个森林的图
假设n=4且nums[]={1,2,3,4}则解空间应该是
第一层：1 2 3 4
第二层：12 13 14 /21 23 24/31 32 34
第三层：123 124/132 134/213 214/231 234/241 243/312 314/.....
第四层：略
确定易于搜索的解空间结构
解空间主要对应的是子集树和排列树，依据题意进行选择。（根据题意画个图，就知道了）
什么是子集树？？？
子集树是一个数学学科词汇，属于函数类，当所给问题是从n个元素的集合S中找出S满足某种性质的子集时，相应的解空间称为子集树。
当所给问题是从n个元素的集合S中找出S满足某种性质的子集时，相应的解空间称为子集树。例如：n个物品的0-1背包问题所相应的解空间是一棵子集树，这类子集树通常有2^n个叶结点，其结点总数为(2^(n 1))-1。遍历子集树的算法通常需O(2^n)计算时间。
什么是排列树？？
当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶子节点。因此遍历排列树需要O(n!)的计算时间。
上面已经确定，要将解空间构建成子集树的形式
step 2 回溯法的精髓#
回溯的精髓
退回原状态
如何回退是回溯的精髓，什么时候回退
就本题而言，第一躺全排列应该是1->2->3->4 ,当走到最后一步4之后，应该回退一步到1->2->3因为3只有一个分支4，再回退一步到1->2，然后满足了约束函数可以进行下一步1->2->4;
对于本题，回退到方法在于，标记未被访问的数组下标，回退则重制标记
因此可以使用一个visited[]数组，数组的长度为nums.length，被访问则对应的下标标记为true，否则标记为false；
step 3 回溯函数的设计#
void BackTrace(int t)只传递一个参数的话显然是无法满足本题的，因为本题包含了一下5个需要传递的参数：
- visited[] 数组；
- t 递归深度；
- List<List<Integer>> output 保存所有解的大容器
- List<Integer> save 保存解的小容器
- nums[]原始数据
因此，BackTrace应设计为：
Copypublic static void BackTrace( List<Integer> save, List<List<Integer>> out, boolean visited[], int nums[]) {
if (save.size() == nums.length) {
out.add(new ArrayList<>(save));
return;
} else
for (int i = 0; i < nums.length; i ) {
if (visited[i]) continue;
visited[i] = true;
save.add(nums[i]);
BackTrace( save, out, visited, nums);
save.remove(save.size() - 1);
visited[i] = false;
}
}
怎么写出这段代码需要结合前面的内容反复的思考 =-= 我想了好久才理清楚回溯的思路
回溯法的延伸#
子集问题
题目：
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例：
输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
从上题中我们可以得出结论，这仍然是一道需要使用回溯法的题目。
解空间与解空间结构#
很明显这是一个子集数的解空间结构
假设n=3且nums[]={1,2,3}则解空间应该是
第一层：1 2 3
第二层：12 13/21 23/31 32
第三层：123 132/213 231/312 321/
关键性问题#
- 通过什么方法回退？
- 约束条件是什么？
- 去除重复对象
检测重复
检测重复首先想到的会是哈希表HashMap.因此每一次添加都应该在添加之前查找，如果找到重复则不存入；
约束条件是什么
约束条件应该还是当遍历到最后一个元素时退出？
通过什么方法回退？
由于集合的特殊性。不需要回退；
函数的设计：#
Copypublic static void BackTrack(int t,int[] nums, List<List<Integer>> out, List<Integer> save) {
out.add(new ArrayList<>(save));
for (int i = t; i < nums.length; i ) {
save.add(nums[i]);
BackTrack(i 1,nums, out, save);
save.remove(save.size()-1);
}
}
作者：Nikura44
出处：https://www.cnblogs.com/samanian/p/12194520.html
