計蒜客 T1866 組合的輸出

組合的輸出 時間限制：1S 記憶體限制：131072K

題目連結：組合的輸出

題目描述：

排列與組合是常用的數學方法，其中組合就是從 n 個元素中抽出 r 個元素（不分順序且 r≤n)，我們可以簡單地将 n 個元素了解為自然數 1,2,…,n，從中任取 r 個數。

現要求輸出所有組合。

樣例：

Input：

5 3

Output：

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

AC代碼：

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 26;
int state[N]; // 位置
// bool used[N]; // 數的狀态
int n, m;
void dfs(int step, int start)
{ // start代表下一次該從哪個數字開始選取，即可以起到使組合輸出的數字是從小到大的，也可以起到用數組标記數字避免重複使用的作用。
// step代表目前正在将數放到第step位置。
    if (n + step - start < m) return; // 剪枝，提前結束，節省時間，可有可無。
    if (step == m+1){
        for (int i = 1; i <= m; ++i) printf("%3d", state[i]);
        puts(""); // puts會輸出一段字元串并且自動換行，在這的作用就是起換行符的作用。
        return;
    }
    for (int i = start; i <= n; ++i){
        state[step] = i;
        dfs(step+1, i+1);
        
        state[step] = 0; // 還原狀态，可有可無。（隻是為了說明在遞歸中子操作一般不能影響父狀态）
    }
}
int main(void)
{
    scanf("%d%d", &n, &m);
    dfs(1, 1);
    return 0;
}