首先明确回溯框架的使用范围

• 求解方案（分为两种）

  1.求解方案的种数（楼梯，硬币找零）

  2.求解具体的方案 （硬币找零的方案，八皇后，全排列，子集，组合，数独等）

• 求最优解（一般可以用dp优化）

  如果非要回溯的话，要用备忘录来优化！

框架介绍

1.方案数类

//一般都是这样再添加一些东西
void dfs(int n){
	//递归结束条件
	if(...) {
		res++;
		return;
	}
	for(int i=0;i<n;i++){
		//跳过不符合要求的
		if(...) continue;
		//做选择
		dfs(...);
	}

举个简单例子吧！

上楼梯的问题其实就是回溯问题（可以自己画出递归树，方便理解）

/*3089:爬楼梯

    查看
    提交
    统计
    提问

总时间限制:
    1000ms
内存限制:
    65536kB

描述

    树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数
    例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级
    也可以第一次走两级，第二次走一级，一共3种方法。
输入
    输入包含若干行，每行包含一个正整数N，代表楼梯级数，1 <= N <= 30
输出
    不同的走法数，每一行输入对应一行输出
样例输入

    5
    8
    10

样例输出

    8
    34
    89

*/
#include <iostream>
using namespace std;
void back(int m,int &res){
	//回溯条件，即到了楼底了
	if(m==0){
		// 方案++
		res++;
		return;
	}
	for(int i=1;i<=2;i++){
		// 不符合条件
		if(m-i<0) continue;
		// 做选择
		back(m-i,res);
	}
}

int main(){
	int m;
	while(cin >> m){
		int res = 0;
		back(m,res);
		cout<<res<<endl;
	}
	return 0;
}

值得注意的是这里dfs还需要注意，一般我们记录所有方案的话，就需要选择和撤销选择，来维护节点的属性！

2.具体方案类

举个简单例子就是全排列。

思考一下，选择之后不撤销的话就会对其他子问题的路径记录有影响！

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
vector<vector<int> > res;
void dfs(vector<int> nums,vector<int>& track);
int main(){
	vector<int> nums;
	for(int i=1;i<=3;i++){
		nums.push_back(i);
	}
	vector<int> track;
	dfs(nums,track);
	vector<vector<int> >::iterator iter;
	for(iter=res.begin();iter!=res.end();iter++){
		vector<int> in = *iter;
		vector<int>::iterator iter2;
		for(iter2=in.begin();iter2!=in.end();iter2++){
			cout<<*iter2;
		}
		cout<<endl;
	}
}
// nums为选择，track为路径 
void dfs(vector<int> nums,vector<int>&track){
	if(track.size()==nums.size()){
		//将当前的路径加入到res 
		res.push_back(track);
		return;
	}
	
	for(int i=0;i<nums.size();i++){
		//用路径进行剪枝
		if(count(track.begin(),track.end(),nums[i])) continue;
		//选择
		track.push_back(nums[i]);
		dfs(nums,track);
		//撤销
		track.pop_back();
	}
}

再来一个李白喝酒问题

题目描述：

李白街上走，提壶去买酒，遇店加一倍，见花喝一斗”，途中，遇见5次店，见了10此花，壶中原有2斗酒，最后刚好喝完酒，要求最后遇见的是花，求可能的情况有多少种？

题解：

#include <iostream>
#include <vector>
#include <list>
using namespace std;
void dfs(int jiu,int hua,int dian);
int res = 0;
int main(){
	int jiu = 2;
	int hua = 10;
	int dian = 5;
	dfs(jiu,hua,dian); 
	cout<<res;
} 

void dfs(int jiu,int hua,int dian){
	//结束条件
	if(jiu==1&&hua==1&&dian==0){
		res++;
		return;
	}
	if(hua>0){
		dfs(jiu-1,hua-1,dian);
	}
	if(dian>0){
		dfs(jiu*2,hua,dian-1);
	}
}

这是我目前总结的经验，后续遇见其他的还会补充的！不懂的可以问我这个小菜鸡！