递归真的不大好理解，而且很难自己写出来，但是我发现牛逼的算法都会用到递归=_=不知道到底是什么样的人才能发明递归这种东西，他的脑神经是不是用二进制构成的=_=
言归正传
回溯算法是一种做决策的算法，也叫试探法。基本思想是：按一条路往前走，能进则进，不能进则退回来换一条路再试。回溯一般可以用树的概念来描述。回溯法就是从树的根节点出发（注意：根节点不包含任何元素，根节点的子节点包含所有元素，这样才能对每个元素一一作出选择），按深度优先遍历经过一系列结点，到达叶节点的过程。每到达一个结点就可以看做得出一个解，然后选择一个满足要求的结点。其本质是加了约束条件的枚举法！
步骤：
（1）定义问题的解空间，这个解空间必须至少包含问题的一个最优解。（就是找出最优子结构）
（2）组织解空间，就是构建一棵树或者一个图
（3）按深度优先的方式搜索问题的解，并用剪支函数（添加约束条件）来避免去搜索一个无效的解。
回溯的套路（一定要记住）：
Backtrack(层数i){ if(i>总层数){ 输出; } else{ 左子树处理； //约束条件1，然后push Backtrack(层数+1)； 右子树处理； //约束条件2，然后pop Backtrack(层数+1); } }实战：
1、求一组数据的幂集，即把数据的所有子集全部列出来，有2^n个。比如{1,2,3}的子集有[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]. 参考的是博客http://blog.csdn.net/ffmpeg4976/article/details/45007439
#include <iostream> #include <vector> #include <stdlib.h> using namespace std; vector<vector<int>>result; vector<int>temp; void backtrack(vector<int>&S,int i){ cout<<"i="<<i<<endl; if(i==S.size()){ result.push_back(temp); return; } temp.push_back(S[i]); backtrack(S,i+1); temp.pop_back(); backtrack(S,i+1); return; } int main(){ vector<int>v; int n; cin>>n; cout<<"\n"; for(int i=0;i<n;i++){ int p; cin>>p; v.push_back(p); } backtrack(v,0); cout<<"result:"<<endl; for(int i=0;i<result.size();i++){ vector<int>cnt(result[i]); for(int j=0;j<cnt.size();j++){ cout<<cnt[j]<<" "; } cout<<"\n"; } system("pause"); return 0; }
2、著名的N皇后问题：在一个NxN的棋盘上放置n个皇后，使得n个皇后不在同一行，同一列，同一对角线。参考大神博客http://blog.csdn.net/hackbuteer1/article/details/6657109 //伪代码。 这里用到了我上次有写的for循环加递归的方法。 运算量较大，所以n皇后一般都是用for循环，不用递归。 void queen(int row) { if (n == row) //如果已经找到结果，则打印结果 print_result(); else { for (k=0 to N) { //试探第row行每一个列 if (can_place(row, k) { place(row, k); //放置皇后 queen(row + 1); //继续探测下一行 } } } } 3、回溯法的应用还有：0/1背包问题，着色问题，旅行商问题等。
