回溯算法
回溯法
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。也可以称为剪枝点，所谓的剪枝，指的是把不会找到目标，或者不必要的路径裁剪掉。
许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。
若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
除过深度优先搜索，常用的还有广度优先搜索。
深度优先搜索（Depth First Search）------ 一条道走到黑
同学们先思考这样一个问题：
假如有编号为1~3的3张扑克牌和编号为1~3的3个盒子，现在需要将3张牌分别放到3个盒子中去，且每个盒子只能放一张牌，一共有多少种不同的放法。
当走到一个盒子面前的时候，到底要放那一张牌呢？在这里应该把所有的牌都尝试一遍。假设这里约定一个顺序，按牌面值从小到大依次尝试。在这样的假定下，当走到第一个盒子的时候，放入1号牌。
放好之后，继续向后走，走到第二个盒子面前，此时还剩2张牌，牌面值最小的为2号牌，按照约定的规则，把2号牌放入第二个盒子。
此时，来到第三个盒子面前，只剩一张牌，放入第三个盒子。此时手中的牌已经用完。
继续向后走，走到了盒子的尽头，后面再也没有盒子，并且也没有可用的牌了，此时，一种放法已经完成了，但是这只是一种放法，这条路已经走到了尽头，还需要折返，重新回到上一个盒子。
这里回到第三个盒子，把第三个盒子中的牌取出来，再去尝试能否再放其它的牌，这时候手里仍然只有一张3号牌，没有别的选择了，所以还需要继续向后回退，回到2号盒子面前。
收回2号盒子中的2号牌，现在手里有两张牌，2，3，按照约定，再把3号牌放入2号盒子，放好之后，继续向后走，来到3号盒子。
此事手里只有一张2号牌，把它放入3号盒子，继续向后走。
此时这条路又一次走到了尽头，一个新的放法又产生了，继续向上折返，尝试其它可能，按照上述步骤，依次会产生所有结果。
代码如何实现这种过程呢？最主要的事情，向面前的盒子里放每一种牌，一个for循环搞定。这里还需考虑，现在手里有没有这张牌，用一个数组st标记手里是否有这张牌
#include<iostream> using namespace std; const int N=10; int n; int path[N]; bool st[N]; void dfs(int u) { if(u==n) { for(int i=0;i<n;i++) cout<<path[i]<<" "; puts(""); return ; } for(int i=1;i<=n;i++) { if(!st[i]) { path[u]=i; st[i]=true; dfs(u+1); st[i]=false; } } } int main() { cin>>n; dfs(0); return 0; }
输入样例：
3
输出样例：
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
示例1.dfs带权值的n叉树
/* // Definition for Employee. class Employee { public: int id; int importance; vector<int> subordinates; }; */ class Solution { public: int dfs(unordered_map<int,Employee*>& info,int id) { int num=info[id]->importance;//领导（子根节点） for(const auto& sid:info[id]->subordinates) { num+=dfs(info,sid);//加上其直系下属 } return num; } int getImportance(vector<Employee*> employees, int id) { if(employees.empty()) return 0; unordered_map<int,Employee*> info;//用哈希存储唯一id对应的信息 for(const auto& e: employees) info[e->id]=e; return dfs(info,id); } };
示例2.dfs查找所有连接方块
思路：
非常简单，就是把图块的四个方向都搜索一遍，对于每个相邻的同色图块修改成新色即可
我们从给定的起点开始，进行深度优先搜索。每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格的颜色更新，以防止重复搜索；如果不相同，则进行回溯。
注意：因为初始位置的颜色会被修改，所以我们需要保存初始位置的颜色，以便于之后的更新操作。
class Solution { public: const int dx[4]={1,-1,0,0}; const int dy[4]={0,0,1,-1}; void dfs(vector<vector<int>>& image,int x,int y,int old,int color) { if(image[x][y]==old) { image[x][y]=color; for(int i=0;i<4;i++) { int mx=x+dx[i],my=y+dy[i]; if(mx>=0&&mx<image.size()&&my>=0&&my<image[0].size()){ dfs(image,mx,my,old,color);//在范围内则继续搜索 } } } } vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) { int old=image[sr][sc];//原来颜色 if(old!=color) dfs(image,sr,sc,old,color); return image; } };
示例3.逐一遍历变量并组合
思路：
先按题意打表存储所有字符串，然后按digits数字循序提取数字所对应的字符串，按序提取每个字母利用递归组合，当深度（id）达到digits的长度时，即完成了一个排列组合，回溯上述操作得到所有排列组合。
string nums[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; class Solution { public: void dfs(string& digits,int id,string str,vector<string>& ret) { if(id==digits.size()) { ret.push_back(str); return ; } int num=digits[id]-'0'; string cur=nums[num]; for(auto& ch:cur) { dfs(digits,id+1,str+ch,ret); } } vector<string> letterCombinations(string digits) { vector<string> ret; if(digits.empty()) return ret; dfs(digits,0,"",ret); return ret; } };
示例4.dfs构造排列组合
此题相加的元素可以重复，所以去下一个元素的位置可以从当前位置开始， DFS + 回溯
为了保证组合不重复(顺序不同，元素相同，也算重复)，不再从当前位置向前看
1. 从第一个元素开始相加
2. 让局部和继续累加候选的剩余值
3. 局部和等于目标值，保存组合，向上回退，寻找其它组合
class Solution { public: void dfs(vector<int>& candidates,int target,vector<vector<int>>&res, vector<int>& path,int sum,int start) { if(sum>target) return ; if(sum==target) res.push_back(path); for(int i=start;i<candidates.size();i++) { //单个值已经大于目标，直接跳过（剪枝避免数据重复） if(candidates[i] > target) continue; path.push_back(candidates[i]);//按序尝试路径 dfs(candidates,target,res,path,sum+candidates[i],i); path.pop_back();//回溯 } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> res;//符合条件的组合 vector<int> path;//查找组合的路径 int sum=0,start=0; dfs(candidates,target,res,path,0,0); return res; } };
小小练手.去重全排列
思路：
此题组合的长度不唯一，最小组合长度为1， 最大组合长度为tiles的长度。
按照题意tiles中每一个位置的字符在组合中只能出现一次， 所以可以用一个标记辅助
当去组合新的组合时，可以与tiles中的每一个位置组合，但是如果当前位置已经在当前组合中出现过，则跳过
虽然此题中每一个位置的字符在组合中只能出现一次，但是tiles中可能有相同的字符，所以需要考虑重复的组合
而unordered_set可以天然去重，可以用其去重
DFS + 回溯：
当前组合不为空, 则插入set中
继续给当前组合拼接新的组合，尝试拼接tiles每一个位置的字符
如果当前位置已在组合中出现过，返回到2，否则标记当前位置，继续拼接更长的组合
回溯，尝试组合其它位置，返回2
当所有位置都已经使用过时，当前递归就结束了，继续向上层DFS回退
最终返回set的大小即为组合数目。
class Solution { public: void dfs(string& tiles,string s,vector<int>& st,unordered_set<string>& tot) { if(!s.empty()) tot.insert(s);//只要有就算一种 for(int i=0;i<tiles.size();i++) { if(st[i]) continue; st[i]=1; dfs(tiles,s+tiles[i],st,tot); st[i]=0; } } int numTilePossibilities(string tiles) { if(tiles.empty()) return 0; unordered_set<string> tot;//利用set性质去重 vector<int> st(tiles.size(),0);//状态，表示有无用过 dfs(tiles,"",st,tot); return tot.size(); } };
