P1157-组合的输出

题目链接

组合的输出，不论是在算法题目中，还是日常编程中都十分常遇到

题目

题目描述

输入格式

输出格式

输入输出样例

输入 #1

5 3 

输出 #1

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

代码

#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <vector>
using namespace std;

int n, r;
int num[100]; //满足100位元素

//k表示当前正在计算第k位
void dfs(int k)
{
    //如果k超过了元素数
    if (k > r)
    {
        //输出当前组合
        for (int i = 1; i <= r; i++)
        {
            cout << setw(3) << num[i];
        }
        cout << endl;
        return;
    }
    //如果没超过元素数，则从k+1位开始搜索
    for (int i = num[k - 1] + 1; i <= n; i++)
    {
        num[k] = i;
        dfs(k + 1);
    }
}

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

题目分析

从n个数获得r个元素的组合，采用dfs深度优先搜索，从第1位搜到第r位，每一位都不超过n，一旦超过了所需元素数，便输出当前组合，接着从上一位开始，加1后继续搜索