摘要：什么是回溯算法回溯法是一种系统搜索问题解空间的方法。解空间定义为与数字长度相同。最后，为什么要掌握回溯法因为懂了回溯法之后笔试里的很多题就算不了，起码成功运行到之间是没问题的。
什么是回溯算法？
回溯法是一种系统搜索问题解空间的方法。为了实现回溯，需要给问题定义一个解空间。
说到底它是一种搜索算法。只是这里的搜索是在一个叫做解空间的地方搜索。
而往往所谓的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维位置的解，然后保证最后一维中位置是终点即可。
如果仍然觉得抽象，那么我建议大家把回溯想象成“填格子”游戏。
到leetcode上找回溯的专题，对于每一个回溯法可解的问题，看看这题需要填的格子(格子就是解空间)是什么。
比如n个不重复字母的全排列，不就是填充n个格子，填满并且合法就得到一个解。
再比如在字母矩阵中搜索某个字符串比如"adrsad",那么格子有几维？不就是填充维度是n的格子(字符串s长度n)，并且格子的第i(i从0开始到n-1)个维度上必须填s[i]，否则都是不合法的。用这种思路再做这个题看看会不会好做很多。
再比如括号生成，这里的格子的数量是括号对数乘以2，格子上填的就是左括号或者右括号，这里的剪枝条件是，当前右括号数量超过了左括号，或左括号数量超过了一半。当然为了剪枝需要在函数参数中维护左右括号数这两个变量。
最后，为什么要掌握回溯法？？？
因为懂了回溯法之后笔试里的很多题就算AC不了，起码成功运行70%到90%之间是没问题的。
而且如果笔试题里有的数据集设计的不够好，那么回溯甚至可以比动态规划运行的还快。
而这对于获得面试机会已经足够了！！！
并且回溯很优美，很容易理解，因为说到底它不过就是个填格子的游戏罢了。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/73446.html
摘要：输入输出分析题目由于我们需要找到多个组合，简单的使用循环肯定是不行的，这时候我们可以使用回溯算法来解决这个问题。用回溯算法解决问题的一般步骤针对所给问题，定义问题的解空间，它至少包含问题的一个最优解。 题目描述 Given a set of candidate numbers (candidates) (without duplicates) and a target number ...
摘要：回溯算法在算法过程中就是类似于枚举算法，尝试在搜索过程中找到问题的解。 回溯算法( BackTrack )在算法过程中就是类似于枚举算法，尝试在搜索过程中找到问题的解。 使用回溯算法解题的一般步骤 使用回溯算法解题的一般步骤： 针对所给问题得出一般的解空间 用回溯搜索方法搜索解空间 使用深度优先去搜索所有解并包含适当的剪枝操作 LeetCode 使用回溯算法的题目主要有 36 题，...
摘要：用来存放每一个可能的结果最终结果深度优先遍历剪枝当遍历到底个数是，如果的元素个数剩余元素个数时，就不满足条件了中元素个数达到，表示深度优先遍历到达最深处了。 77. 组合77. 组合77. 组合 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任...
摘要：例如题目解析题目的意思很明显，就是把两个数字加起来，需要考虑进位的情况。总结这个题目如果都能独立完成，那么水平已经可以足以应付国内各大企业的算法面。 欢迎大家前往腾讯云+社区，获取更多腾讯海量技术实践干货哦~ 本文由落影发表 前言 LeetCode上的题目是大公司面试常见的算法题，今天的目标是拿下5道算法题： 题目1是基于链表的大数加法，既考察基本数据结构的了解，又考察在处理加法过程中...
阅读 2414·2021-09-01 10:41
阅读 1438·2019-08-30 14:12
阅读 506·2019-08-29 12:32
阅读 2855·2019-08-29 12:25
阅读 2933·2019-08-28 18:30
阅读 1703·2019-08-26 11:47
阅读 972·2019-08-26 10:35
阅读 2585·2019-08-23 18:06
