写在最前
相信在你们不懈的努力之下，基本的递归一定可以写出来了，那么我们现在就来看看递归的升级版——回溯怎么写吧！
简说回溯
递归是一种特别重要的解题策略。大部分题目需要找到最优解，而这个求解过程可能存在一定的规律性，比如贪心，递推等，但是大部分情况可能只能暴力枚举所有情况找到答案，而暴力枚举这个过程简单的可以用循环实现，但是对于一些比较复杂的情况，需要用递归来实现。
比如数独游戏，在最开始的时候，每个空格子有很多种可能，我们需要先尝试填入一个数，在此基础上再去尝试填入其他格子，在填数过程中，我们会发现当前这种方案可能是错误的，那么我们就需要返回上一步，重新尝试其他可能，这种解题办法我们称为回溯法。
还是老样子，直接用例题来提高熟练度
全排列问题
全排列问题
题目描述
按照字典序输出自然数 1 1 1 到 n n n 所有不重复的排列，即 n n n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
输入格式
一个整数 n n n。
输出格式
由 1 ∼ n 1 \sim n 1∼n 组成的所有不重复的数字序列，每行一个序列。
每个数字保留 5 5 5 个场宽。
样例 #1
样例输入 #1
3
样例输出 #1
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
提示
1 ≤ n ≤ 9 1 \leq n \leq 9 1≤n≤9。
全排列问题是数学上的一类经典问题，在数学上存在排列公式可以直接快速求解。
但是在实际问题中可能存在一些其他的限制条件，比如某个位置不能放某个数，某个数必须放在某个位置，这种情况下用公式就比较麻烦，所以先考虑一种比较效率低下但是比较万能的方法。
简单来说就是对于每一个位置，依次放入一个之前未使用过的数，当把所有数都放入之后，就表示存在一种答案，当把每个位置的所有情况都尝试之后，累加得到的答案就是正确答案。
我们可以把该题看做有n个格子，依次要把n个数放入这些格子中。对于每一个格子而言，放数的方法都是相同的——找到一个之前未放入的数。
那么我们如何才能知道这个数是否已经使用过了呢？比较简单的办法就是开一个book数组，标记1—n中每一个数的状态。
每次放数的时候，需要考虑两个问题。
第一：所有情况都不能遗漏，即从1枚举到n。
第二：之前放过的数不能重复放，即未被标记。
当n个格子中都有数的时候表示放数结束，得到一种正确方案，记录答案并返回。
前面的做法只考虑了一种情况，比如n=3的时候，找到的第一种排列为1 2 3，接下来我们应该先考虑第3个格子是否还可以放其他数，发现不可以放其他数，那么应该继续返回上一次，即回到第二个格子，第二个格子之前放了数字2，我们考虑是否可以放下一个数字3，发现可以，当第二个格子放了数字3之后，继续考虑第三个格子，发现可以放数字2，此时又找到一种可能的情况。接着继续返回尝试其他可能，当返回到第一个格子的时候，发现可以放数字2，继续到第二个格子，可以放数字1，到第三个格子，可以放数字3，又是一种情况…一次尝试和返回，直到返回主函数为止。
ACcode
#include <bits/stdc++.h>
using namespace std;
int tmp[100];
bool used[100];
void dfs(int n,int step){
if (step==n){
for (int i=0;i<n;i++){
printf("%5d",tmp[i]);
}
cout<<endl;
return;
}
for (int i=1;i<=n;i++){
if (used[i]==0){
tmp[step]=i;
used[i]=1;
dfs(n,step+1);
used[i]=0;//回溯
}
}
}
int main() {
int n;
cin>>n;
dfs(n,0);
return 0;
}
借书问题
对于输入的每个同学喜欢的书的情况，可以开一个二维数组来表示，a[i][j]表示第i位同学是否喜欢第j本书。
对于每一个同学是否可以借这一本书，考虑的情况都是相同的：
（1）这本书是否存在
（2）第i个同学是否喜欢这本书
（3）这本书是否已经在前面被借走了。
当这n位同学都可以借到一本书，那么就表示这种方案是合理的，如果某位同学无书可以借，那么就说明这种方案是错误的，就需要返回上一位同学重新借其他书。
该题还需要输出借书的方案，即我们需要记录每位同学借了哪一本书，再开一个b数组，b[i]=j表示第i位同学借了第j本书。
由于方案不止一种，输出的方案需要按照字典序排列。即前面的同学先借编号小的书，那么我们在枚举的时候就只能从1开始枚举到n，这样得到的可行方案就是按照字典序从小到大排列的。
还有一些题目要求按照字典序从大到小排列，即前面的同学先借编号大的书，这种情况我们需要从n到1枚举。
ACcode
#include<bits/stdc++.h>
using namespace std;
int n,a[15][15],cnt;
int ans[1000][15],b[15],used[20];
inline int read(){
int x=0;
char ch=0;
while (ch>'9'||ch<'0')ch=getchar();
while (ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
return x;
}
void dfs(int k){
if (k==n){
for (int i=0;i<n;i++){
ans[cnt][i]=b[i];
}
cnt++;
}else {
for (int i=0;i<n;i++){
if (used[i]==0&&a[k][i]==1){
used[i]=1;
b[k]=i+1;
dfs(k+1);
used[i]=0;
}
}
}
}
int main(){
n=read();
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
cin>>a[i][j];
}
}
dfs(0);
cout<<cnt<<endl;
for (int i=0;i<cnt;i++){
for (int j=0;j<n;j++){
cout<<ans[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
好了，基础的部分已经搞完了，现在我们来看看组合问题
前面我们遇到的问题都是用回溯法求解排列类问题，即选择相同的元素，但是顺序不同算不同的方案。很多时候还会出现另一类问题——组合数问题。即从n个元素中选择m个元素的一个组合，组合和排列的区别在于，组合和顺序没有关系只要每个元素都相同，顺序不同也只算作一种方案，即1,1,5和5,1,1是一个相同的组合。
组合的输出
题目描述
排列与组合是常用的数学方法，其中组合就是从 n n n 个元素中抽出 r r r 个元素（不分顺序且 r ≤ n r \le n r≤n），我们可以简单地将 n n n 个元素理解为自然数 1 , 2 , … , n 1,2,\dots,n 1,2,…,n，从中任取 r r r 个数。
现要求你输出所有组合。
例如 n = 5 , r = 3 n=5,r=3 n=5,r=3，所有组合为：
123 , 124 , 125 , 134 , 135 , 145 , 234 , 235 , 245 , 345 123,124,125,134,135,145,234,235,245,345 123,124,125,134,135,145,234,235,245,345。
输入格式
一行两个自然数 n , r ( 1 < n < 21 , 0 ≤ r ≤ n ) n,r(1<n<21,0 \le r \le n) n,r(1<n<21,0≤r≤n)。
输出格式
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
注意哦！输出时，每个数字需要 3 3 3 个场宽。以 C++ 为例，你可以使用下列代码：
cout << setw(3) << x;
输出占
3
3
3 个场宽的数
x
x
x。注意你需要头文件 iomanip。
样例 #1
样例输入 #1
5 3
样例输出 #1
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
该题的解题策略和前面类似，都是用回溯法尝试所有可能性，找出符合条件的所有方案，但是该题也有和前面不一样的地方，如果按照前面的方式枚举，那么最终得到的答案肯定是有重复的，而且重复了很多次，那么有没有办法避免这种重复的情况呢？要怎么样枚举才能避免重复情况呢？
根据题目的输出我们可以发现，下一个数一定是大于前一个数，这就是一种很好的避免重复的办法，只要我们保证了下一个数大于前一个数，这样一个组合的满足要求的排列有且仅有一个，而且刚好满足字典序最小的要求。
ACcode
#include <bits/stdc++.h>
using namespace std;
int r, n;
int temp[21];
void print () {
for (int i = 0; i < r; i++) {
printf("%3d", temp[i]);
}
cout << endl;
}
void f(int start, int k ) { //k 还有多少个数字没有选
if (k == 0) {
print();//打印结果
return;
}
for (int i = start; i <= n ; i++) {
temp[r - k] = i;
f(i + 1, k - 1);
}
}
int main() {
cin >> n >> r;
f(1, r);
return 0;
}
放苹果
题目描述
把 m m m 个同样的苹果放在 n n n 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法。（ 5 , 1 , 1 5,1,1 5,1,1 和 1 , 1 , 5 1,1,5 1,1,5 是同一种方法）
输入格式
第一行是测试数据的数目 t t t，以下每行均包括二个整数 m m m 和 n n n，以空格分开。
输出格式
对输入的每组数据 m m m 和 n n n，用一行输出相应的结果。
样例 #1
样例输入 #1
1
7 3
样例输出 #1
8
样例 #2
样例输入 #2
3
3 2
4 3
2 7
样例输出 #2
2
4
2
提示
对于所有数据，保证： 1 ≤ m , n ≤ 10 1\leq m,n\leq 10 1≤m,n≤10， 0 ≤ t ≤ 20 0 \leq t \leq 20 0≤t≤20。
根据题目中的要求，该题仍然是一道组合数问题，即跟选中元素的顺序无关，所以枚举的时候保证下一个元素大于等于下一个元素即可，注意这里可以等于。
但是该题的结束条件有点不一样，当n个盘子都放了苹果之后是不是就一定是一种正确方案了呢？并不是，因为还要保证苹果必须要放完，所以我们还需要记录剩余的苹果数量（或者已经放了的苹果数量）。
同样，当前盘子可以放的苹果数量的范围为k到剩余苹果的数量，甚至还可以精确到剩余苹果数量除以剩余盘子数量。
#include <bits/stdc++.h>
using namespace std;
int t;
int sol(int m, int n) { //m为苹果，n为盘子
if (n == 1 || m == 0)
return 1;
if (m < n)
return sol(m, m);
if (m >= n)
return sol(m, n - 1) + sol(m - n, n);
}
int main() {
cin >> t;
int m, n;
for (int i = 1; i <= t; i++) {
cin >> m >> n;
cout << sol(m, n) << endl;
}
return 0;
}
烤鸡
题目背景
猪猪 Hanke 得到了一只鸡。
题目描述
猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 10 10 10 种配料（芥末、孜然等），每种配料可以放 1 1 1 到 3 3 3 克，任意烤鸡的美味程度为所有配料质量之和。
现在， Hanke 想要知道，如果给你一个美味程度 n n n ，请输出这 10 10 10 种配料的所有搭配方案。
输入格式
一个正整数 n n n，表示美味程度。
输出格式
第一行，方案总数。
第二行至结束， 10 10 10 个数，表示每种配料所放的质量，按字典序排列。
如果没有符合要求的方法，就只要在第一行输出一个 0 0 0。
样例 #1
样例输入 #1
11
样例输出 #1
10
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 2 1 1 1 1
1 1 1 1 2 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1
1 1 2 1 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1
提示
对于 100 % 100\% 100% 的数据， n ≤ 5000 n \leq 5000 n≤5000。
该题的解题思路比较简单，对于每一种调料，考虑[1,4]两种情况，主要在于时间复杂度的优化。
因为每种调料的范围是[1,4]，在考虑当前第i种调料的时候，之前调料和为sum，需要满足第一个条件是sum+i+(10-step)<=n,即后面每种调料至少要放1g，一共是（10-step）g，还需要满足第二个条件是sum+i+4*(10-step)>=n，即后面每种调料最多放4g。
对于回溯类题目，由于比赛中爆搜一般都不是正解，所以我们要尽可能优化搜索的效率，这样才能得到更高的分数，需要考虑前面是否合理以及后面是否合理。
但是这里作者偷了个懒，你看代码就知道了
#include <bits/stdc++.h>
using namespace std;
int main() {
int a,b,c,d,e,f,g,h,i,j,in,x=0;
cin>>in;
for (a=1;a<=4;a++) {
for (b=1;b<=4;b++) {
for (c=1;c<=4;c++) {
for (d=1;d<=4;d++) {
for (e=1;e<=4;e++) {
for (f=1;f<=4;f++) {
for (g=1;g<=4;g++) {
for(h=1;h<=4;h++) {
for (i=1;i<=4;i++) {
for (j=1;j<=4;j++) {
if (a+b+c+d+e+f+g+h+i+j==in){
x++;
}
}
}
}
}
}
}
}
}
}
}
cout<<x<<endl;
for (a=1;a<=4;a++){
for (b=1;b<=4;b++){
for (c=1;c<=4;c++){
for (d=1;d<=4;d++){
for (e=1;e<=4;e++) {
for (f=1;f<=4;f++) {
for (g=1;g<=4;g++) {
for(h=1;h<=4;h++) {
for (i=1;i<=4;i++) {
for (j=1;j<=4;j++) {
if (a+b+c+d+e+f+g+h+i+j==in){
cout<<a<<" ";
cout<<b<<" ";
cout<<c<<" ";
cout<<d<<" ";
cout<<e<<" ";
cout<<f<<" ";
cout<<g<<" ";
cout<<h<<" ";
cout<<i<<" ";
cout<<j<<endl;
}
}
}
}
}
}
}
}
}
}
}
return 0;
}
OK哈，这就是所有的回溯算法，再找个时间吧最后一部分写了就可以完结了！
