#include <bits/stdc++.h>
using namespace std;

const int Kenton = 250;
int n, r, a[Kenton];

void dfs(int step)
{
	if (step > r)
	{
		for (int i = 1; i <= r; i++) cout << a[i] << " "; // 输出答案 
		cout << endl; // 记得输出空行 
		return;
	}
	for (int i = a[step - 1] + 1; i <= n; i++)
	{
		a[step] = i;
		dfs(step + 1);
	}
}

int main()
{
	cin >> n >> r; // 输入n,r 
	dfs(1); // 进行深度优先搜索 
	return 0;
}

/*
好吧，其实这题真的很水。。。
想不到有什么可以写的注释 
可以当作dfs的第一题 
*/ 

#include<iostream>
using namespace std;
int n,r;
int a[114];//存储每数
bool vis[514];//标记是否用过
void dfs(int k)
{
	if(k>r)//足够长的时候
	{
		for(int i=1;i<=r;i++)//输出
		{
			cout<<a[i]<<" ";
		}
		cout<<endl;
		return;//结束
	}
	for(int i=a[k-1]+1;i<=n;i++)//取下一个数
	{
		if(!vis[i])//没探索过时
		{
			a[k]=i;//记录这个数字
			vis[i]=1;//标记
			dfs(k+1);//递归
			vis[i]=0;//回溯,恢复操作
		}
	}
}
int main()
{
	cin>>n>>r;//输入
	dfs(1);//从头开始
	return 0;//完结散花
}

题意

有 $n$ 个数，求 $r$ 个数的全排列

PS：排列要升序

思路

hhh，升序的全排列

和正常的全排列一样，但到 $r$ 就可以输出了。而且由于是升序的，连检查数组都不用了

代码

#include <bits/stdc++.h>
using namespace std;
int n,r;
int a[250];
void dfs(int u){
	if (u > r){
		for (int i = 1;i <= r;i++){	// 这里到 r 就可以了
			printf("%d ",a[i]);
		}
		cout << "\n";
		return;
	}
	for (int i = a[u - 1] + 1;i <= n;i++){	// 从小到大排
		a[u] = i;
		dfs(u + 1);	// 这里不用判断，因为不会查到前面用的（升序）
	}
}
int main(int argc, char **argv){
	cin >> n >> r;
	dfs(1);	// 索引从 1 开始，不然只能 30 WA
	return 0;
}

简单的小题，===

#include<bits/stdc++.h>
using namespace std;
int n,r,arr[31];
bool check(int b,int a){
    if(b==0) return 0;
    for(int i=1;i<=a;i++){
        if(arr[i]==b) return 0;
    }
    return 1;
}
void dfs(int a){
    if(a==r){
        for(int i=1;i<=r;i++) cout<<arr[i]<<' ';
        cout<<'\n';
        return;
    }
    for(int i=arr[a];i<=n;i++){
        if(check(i,a)){
            arr[a+1]=i;
            dfs(a+1);
            arr[a+1]=0;
        }
    }
}
int main(){
    cin>>n>>r;
    dfs(0);
    return 0;
}

easy~

#include <iostream>
using namespace std;

int n, r;
int a[25];
bool visited[25];
void dfs(int k)
{
	if(k > r)
	{
		for(int i = 1; i <= r; i++)
			cout << a[i] << " ";
		cout << endl;
		return;
	}
	for(int i = a[k-1] + 1; i <= n; i++)
	{
		if(!visited[i])
		{
			a[k] = i;
			visited[i] = 1;
			dfs(k + 1);
			visited[i] = 0;
		}
	}
}

int main()
{
	cin >> n >> r;
	dfs(1);
	return 0;
}

题意

将$C_n^r$的结果全部输出

死路

没有，根本不会。

致谢

曾腹肌老师的提醒：全排列。

思路

每一个都排列没有用过的数字。

70分TLE歹马

#include<iostream>
using namespace std;
int n,r;
int a[21];
bool b[21];
int main(){
	cin>>n>>r;
	void dfs(int);
	dfs(0);
}
void dfs(int k){
	if(k==r){
		for(int i=0;i<k-1;i++)//问题
			if(a[i]>a[i+1])//所
				return;//在
		for(int i=0;i<k;i++)
			cout<<a[i]<<" ";
		cout<<"\n";
	}
	else{
		for(int i=1;i<=n;i++)
			if(!b[i]){
				a[k]=i;
				b[i]=true;
				dfs(k+1);
				b[i]=false;
			}
	}
}

问题

每次输出还要确定大小顺序

再谢

看了潘伟明的题解的我

大受启发

解决

对于每1步，从前往后数，就可以避免大小顺序问题。

AC歹马

#include<iostream>
using namespace std;
int n,r;
int a[21];
bool b[21];
int main(){
	cin>>n>>r;
	void dfs(int);
	dfs(0);
}
void dfs(int k){
	if(k==r){
		for(int i=0;i<k;i++)
			cout<<a[i]<<" ";
		cout<<"\n";
	}
	else{
		for(int i=a[k-1/*注意这里*/]+1;i<=n;i++)
			if(!b[i]){
				a[k]=i;
				b[i]=true;
				dfs(k+1);
				b[i]=false;
			}
	}
}

问题

为什么AC了还是歹马呢？看歹马，/*注意这里*/处如果k=0，k-1就是-1，a[-1]，你懂的~

解决

所以老师指使我，改成1式，就像潘伟明一样

AC代码

#include<iostream>
using namespace std;
int n,r;
int a[21];//数列
bool b[21];//标记
int main(){
	cin>>n>>r;
	void dfs(int);
	dfs(1);//从1开始，防止a[-1]
}
void dfs(int k){
	if(k>r){//0开始用==，1开始用==r+1或者直接>也是可以的

		for(int i=1;i<k;i++)
			cout<<a[i]<<" ";
		cout<<"\n";
	}
	else{
		for(int i=a[k-1]+1;i<=n;i++)
			if(!b[i]){//如果没被标记过
				a[k]=i;
				b[i]=true;
				dfs(k+1);
				b[i]=false;//取消标记
			}
	}
}

彩蛋

这次没有提示，提示都在题解里立，喜。

原来的TLE版本全是我自己想的+曾老师提了嘴全排列，却和潘伟明不谋而合。

后来改代码发现，这个方法想要对，代码和潘伟明的区别就仅限于变量名和格式，悲

所以事先声明，这都是我个人成果，不存在任何抄袭现象。

老师的呆马+整活 👀️

#include<bits/stdc++.h>

#define Genshin int
#define Impact main
#define Start ()
#define kaka cin
#define hepingjingying cout
#define wangluogongzhu bool

using namespace std;

Genshin r, a[25], n;
wangluogongzhu visited[25];
void dfsy(int k){
	if(k > r){
		for(Genshin i = 1; i <= r; i++){
			hepingjingying << a[i] << " ";
		}
		hepingjingying << endl;
		return ;
	}
	for(Genshin i = a[k-1] + 1; i <= n; i++){
		if(!visited[i]){
			a[k] = i;
			visited[i] = 1;
			dfsy(k + 1);
			visited[i] = 0;
		}
	}
}

Genshin Impact Start{
	kaka >> n >> r;
	dfsy(1);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,r;
int a[25];
bool vst[25]={};
void A(int s){
	if(s>r){
		for(int i=1;i<=r;i++) cout<<a[i]<<" ";
		cout<<"\n";
		return;
	}
	for(int i=a[s-1]+1;i<=n;i++){
		if(!vst[i]){
			a[s]=i;
			vst[s]=true;
			A(s+1);
			vst[s]=false;
		}
	}
}
int main(){
	cin>>n>>r;
	A(1);
	return 0;
}

晚了一分钟

AC呆马：

#include <iostream>
using namespace std;

int n, r;
int a[25];
bool visited[25];
void dfs(int k)
{
	if(k > r)
	{
		for(int i = 1; i <= r; i++)
			cout << a[i] << " ";
		cout << endl;
		return;
	}
	for(int i = a[k-1] + 1; i <= n; i++)
	{
		if(!visited[i])
		{
			a[k] = i;
			visited[i] = 1;
			dfs(k + 1);
			visited[i] = 0;
		}
	}
}

int main()
{
	cin >> n >> r;
	dfs(1);
	return 0;
}