回溯法基本思想（回溯法简介）

问题分析使用什么方法？什么是回溯法？怎么使用回溯法？回溯法的具体实施回溯法的延伸

给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:

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