一、問題引出

組合的輸出

題目描述

排列與組合是常用的數(shù)學方法，其中組合就是從 $n$ 個元素中抽出 $r$ 個元素（不分順序且 $r\le n$），我們可以簡單地將 $n$ 個元素理解為自然數(shù) $1,2,\dots ,n$，從中任取 $r$ 個數(shù)。

現(xiàn)要求你輸出所有組合。

例如 $n=5,r=3$，所有組合為：

$123,124,125,134,135,145,234,235,245,345$。

輸入格式

一行兩個自然數(shù) $n,r(1<n<21,0\le r\le n)$。

輸出格式

所有的組合，每一個組合占一行且其中的元素按由小到大的順序排列，每個元素占三個字符的位置，所有的組合也按字典順序。

注意哦！輸出時，每個數(shù)字需要 $3$ 個場寬。以 C++ 為例，你可以使用下列代碼：

cout << setw(3) << x;

輸出占 $3$ 個場寬的數(shù) $x$。注意你需要頭文件 iomanip。

樣例 #1

樣例輸入 #1

5 3

樣例輸出 #1

1  2  31  2  41  2  51  3  41  3  51  4  52  3  42  3  52  4  53  4  5

二、解法一：拼接字符串，然后再cout

毫無疑問，這題肯定是深度優(yōu)先搜索就能解決的問題，但與普通題目存在的一個不同點就是如何去按題中所述的要求去輸出，在方法一當中我采用的是拼接字符串的方式，示意圖如圖所示：圖中的cout并不是真正的cout，而是為了起一個示意的作用，由于篇幅有限，因此我只畫出了一個深度方向上的。

有一個需要注意的點是，題中要求的是set(w)為3并按右對齊輸出，由于我們這里是用字符串拼接的方式進行的，因此需要注意當數(shù)字為1位的時候我們要加2個空格，當數(shù)字為2位時加1個空格，代碼如圖所示：

#include <iostream>
#include <iomanip>
using namespace std;
int n,r,a[22];
void dfs(int m,string s,int startx)
{if (m==r){cout<<s<<endl;return;}for (int i = startx; i <= n; i++){string t;if (a[i]>9){t=" "+to_string(a[i]);}else{t="  "+to_string(a[i]);}dfs(m+1,s+t,i+1);}return;
}
int main()
{cin>>n>>r;for (int i = 1; i <= n; i++){a[i]=i;}dfs(0,"",1);
}

解法二：直接cout

直接cout時，雖然仍是采用深度優(yōu)先的方式，但細節(jié)相比于上面就要做出改變了，

在此解法當中，我們的dfs函數(shù)當中的變量m充當了解法一當中變量m的作用，只不過我們此時是從1開始的（因為我們需要訪問a[k-1]，所以為了防止數(shù)組越界，k的值必須從1開始），此外我們的數(shù)組a的作用也與解法一有很大的不同：解法一的數(shù)組a是寫死的，起一個訪問元素的作用，但在此解法當中是動態(tài)變化的 ，并在每一步當中都對其賦予當前值。最終當我們成功訪問了r個元素的時候我們就輸出。
代碼如下：

#include <iostream>
#include <iomanip>
using namespace std;
int n,r;
int a[22];
void dfs(int k)
{if(k>r){for (int i = 1; i <= r; i++){cout<<setw(3)<<a[i];}cout<<endl;return;}for (int i = a[k-1]+1; i <= n; i++){a[k]=i;dfs(k+1);}
}
int main()
{cin>>n>>r;dfs(1);
}