【題目來(lái)源】
https://www.acwing.com/problem/content/95/
【題目描述】
從 1～n 這 n 個(gè)整數(shù)中隨機(jī)選出 m 個(gè)，輸出所有可能的選擇方案。
【輸入格式】
兩個(gè)整數(shù) n，m，在同一行用空格隔開(kāi)。
【輸出格式】
按照從小到大的順序輸出所有方案，每行 1 個(gè)。
首先，同一行內(nèi)的數(shù)升序排列，相鄰兩個(gè)數(shù)用一個(gè)空格隔開(kāi)。
其次，對(duì)于兩個(gè)不同的行，對(duì)應(yīng)下標(biāo)的數(shù)一一比較，字典序較小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。
【數(shù)據(jù)范圍】
n>0，0≤m≤n，n+(n?m)≤25
【輸入樣例】
5 3
【輸出樣例】
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?
【算法分析】
所有遞歸，都對(duì)應(yīng)一棵遞歸搜索樹(shù)。
遞歸搜索樹(shù)可以讓我們更加容易的理解 DFS。能夠更清晰觀察“層”的概念。
按字典序，從4個(gè)數(shù)中選2個(gè)，得到的遞歸搜索樹(shù)的示意圖如下所示。
?
【算法代碼】文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-631890.html
#include <bits/stdc++.h>
using namespace std;
const int maxn=30;
int n,m;
int path[maxn];
void dfs(int level,int start) {
if(level>m) {
for(int i=1; i<=m; i++) printf("%d ",path[i]);
printf("\n");
} else {
for(int i=start; i<=n; i++) {
path[level]=i;
dfs(level+1,i+1);
}
}
}
int main() {
scanf("%d %d",&n,&m);
dfs(1,1);
return 0;
}
/*
in:
5 3
out:
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
*/
【參考文獻(xiàn)】
https://blog.csdn.net/qq_63391968/article/details/128809355
https://www.acwing.com/video/2731/
?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-631890.html
到了這里，關(guān)于AcWing 93：遞歸實(shí)現(xiàn)組合型枚舉 ← DFS的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
