在老师讲题之前写出来题解电摇一波

免责声明

本题解仅为个人观点，如与标准搜索模板有出入请忽略。标准答案请参考代老师33dai随后提交的程序答案。

搜索与回溯

【搜索与回溯】，又名 【深度优先搜索】 缩写DFS。是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。 ——by 深度优先搜索(DFS)_木可木可❀的博客-CSDN博客_深度优先搜索

搜索与回溯类似于基本的递归，但是由于要考虑到不同的分支，在走到头之后（搜索）需要返回上一步（回溯），类似于走迷宫的不断试错。如下图(美术功底👎 ，见谅 )：

从起点开始逐个遍历搜索，搜索到无法继续走下一步就判断是否搜索到终点，如果是就输出，如果不是就回溯前一步。

明确了基本概念之后，来看一下这一道题

【例5.2】组合的输出

题目：排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。现要求你用递归的方法输出所有组合。

很容易想到，从1到n循环，循环r次（即从1到r位），存储进数组，最后输出。

上代码！（其余要点的写注释）

注意，本题数据存在问题，题目要求每个元素占三个字符的位置，但是测试数据却只是单纯的在每一个元素前面加了俩空格。（这就导致如果当前元素为两位数的话实际上占用了四个字符的位置）

这就导致现在直接提交如下代码只能过40分。

希望代老师能进行修改。

2022/10/1 注：本题数据已修改无误

#include<bits/stdc++.h>
using namespace std;
int n,r,save[1000];  //save数组用于存储答案 
bool pd[1000];  //判断数组 用于判断某个数字有没有被使用 
void print()  //输出函数 
{
	for(int i=0;i<r;i++)
		cout<<setw(3)<<save[i]; //每一位存储的数字 
	cout<<'\n'; //最后换行 
}
void dfs(int i,int qs)  //i为循环次数(或者说当前到第几位），qs为起始的数字
//因为题目要求由小到大的顺序排列，所以第n位一定比第n-1位大 
{
	if(i==r) //循环到r次就停止，然后输出 
	{
		print();
		return;
	}
	else  //如果没有到r次 
	{
		for(int j=qs;j<=n;j++)   
//从前一位的数字开始循环来达到比前一位大的效果 
		{
			if(pd[j]!=1)  //如果这个数字没有被使用过 
			{
				save[i]=j;  //存储进数组中 
				pd[j]=1;  //标记j这个数字被使用过 
				dfs(i+1,j);  //递归调用，同时i+1（位数+1）
				//新的递归函数的qs（起始）就等于这一层调用的j 
				pd[j]=0; //回溯
				//下一层递归结束之后要恢复初始状态
				//即将j标记为未使用的状态 
				save[i]=0;  //并且存储的当前位答案清零 
			}
		}	
	}
}
int main()
{
	cin>>n>>r;  //输入n、r
	//n代表从1到n，r表示输出的一共有几位 
	dfs(0,1);  //搜索函数 
	return 0; 
}

#include <bits/stdc++.h>
using namespace std;
int n, r;
//每个数是否使用过
bool vis[25];
//组合选择的第 i 个数是谁
int ans[25];
//考虑第 now 层（组合的第 now 个数）的操作
//上一个选择的数是 pre
void dfs(int now, int pre)
{
    if (now == r + 1)
    {
        //输出
        for (int i = 1; i <= r; i++)
            cout << "  " << ans[i];
        cout << "\n";
        return;
    }
    //考虑当前层的所有可能
    for (int i = pre + 1; i <= n; i++)
    {
        if (!vis[i])
        {
            //标记一下 i 被使用过了
            vis[i] = true;
            //记录一下选择的第 now 个数是 i
            ans[now] = i;
            //做下一层
            dfs(now + 1, i);
            //还原一下标记
            vis[i] = false;
        }
    }
}
int main()
{
    cin >> n >> r;
    dfs(1, 0);
    return 0;
}