共计 2060 个字符，预计需要花费 6 分钟才能阅读完成。
什么是回溯算法？回溯法是一种系统搜索问题解空间的方法。为了实现回溯，需要给问题定义一个解空间。说到底它是一种搜索算法。只是这里的搜索是在一个叫做解空间的地方搜索。而往往所谓的 dfs，bfs 都是在图或者树这种数据结构上的搜索。根据定义来看，要实现回溯，需要两点 1 搜索，2 解空间先看什么是解空间。就是形如数组的一个向量 [a1,a2,….,an]。这个向量的每个元素都是问题的部分解，只有当这个数组的每一个元素都填满(得到全部解) 的时候，才表明这个问题得到了解答。再看搜索。最简单的就是 for 循环，上面的向量有 n 个维度，因此就是 n 个 for 循环。形如：
for(求 a1 位置上的解)
for(求 a2 位置上的解)
for(求 a3 位置上的解)
……
……
for(求 an 位置上的解)
但是如果 n 是 100？n 是 100000？那么如何回溯？当然也可以写 n 个 for 循环，但是这样的程序会惨不忍睹。。。而且似乎 10000 个(不过往往回溯的时间复杂度太大，一般 n 不会这么大)for 循环也很难写出来。。。因此我们需要一种全新的书写回溯的方法。形如：
void backtrack(int i,int n,other parameters)
{
if(i == n)
{
//get one answer
record answer;
return;
}
// 下面的意思是求解空间第 i 个位置上的下一个解
for(next ans in position i of solution space)
{
backtrack(i+1,n,other parameters);
}
}
就是这么简单！！！上面的模板适用于所有 ” 解空间确定 ” 的回溯法的问题！！！上面的 i 代表解空间的第 i 个位置，往往从 0 开始，而 n 则代表解空间的大小。每一次的 backtrack(i,n,other)调用, 代表求解空间第 i 个位置上的解。而当 i = n 时，代表解空间上的所有位置的解都已经求出。有了上述模板，我们就解决了搜索的问题。因此几乎所有回溯的问题的难度都在于如何定义解空间。下面通过题目，带入模板，然后再看我的解答，来感知一下如何定义解空间。全排列 https://segmentfault.com/a/11… 即对没有重复数字的数组 a =[a1,a2,a3,…an]求全排列。解空间定义为 s =[s1,s2,s3,….sn]与数字长度相同。s 的每一个元素 s【i】(i >= 0&&i < n), 都为数组 a 中的任意元素 a【j】(j >= 0&&j < n)，不过要保证任意的 s【i】不相等。这里唯一复杂的地方是需要用一个 boolean【】数组来表明哪些数已经用过，这样才能保证任意的 s【i】不相等。因此我们看到，回溯本身是很简单的，单纯的模板套用，难的在于需要根据回溯条件来定义各种别的变量，以及最后结果的记录。
探测路径 https://leetcode-cn.com/probl… (这个下面给出 ac 代码)这个题很难，但是掌握了如何定义解空间之后再做这个题就会感觉是小儿科了。这里的解空间 s = [s1,s2,s3,….sn]中的每一个元素 s【i】代表格子的坐标(x,y), 因此从逻辑上来看，s 应该是一个类类型的数组。不过，这个题求的是数目，而不是最后的确切路径，因此解空间在这里并没有记录。java ac 代码：
class Solution {
int ans;
public int uniquePathsIII(int[][] grid) {
if(grid.length == 0)return 0;
int num = 0;
int x = 0,y = 0;
for(int i = 0;i < grid.length;i++)
for(int j = 0;j < grid[0].length;j++){
if(grid[i][j] == 1||grid[i][j] == 0)num++;
if(grid[i][j] == 1){x = i;y = j;}
}
backtrack(0,num,x,y,grid,new boolean[grid.length][grid[0].length]);
return ans;
}
void backtrack(int i,int n,int x,int y,int[][]grid,boolean[][]flag)
{
if(!(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length)||flag[x][y]||grid[x][y] == -1)
return;
if(i == n && grid[x][y] == 2)
{
ans++;
return;
}
flag[x][y] = true;
backtrack(i+1,n,x+1,y,grid,flag);
backtrack(i+1,n,x-1,y,grid,flag);
backtrack(i+1,n,x,y+1,grid,flag);
backtrack(i+1,n,x,y-1,grid,flag);
flag[x][y] = false;
}
}
上面这个题的解空间应该有 N + 1 个才对，但是为了方便书写，我只求出前 n 个位置的解，然后保证最后一个位置是终点即可。
