AcWing-93-组合

2021-01-27 · 45次阅读 · 原创 · 数据结构与算法

#题解 #递归与递推 #算法模板

问题

从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

输入格式

两个整数 n,m ,在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案，每行1个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 5 7排在1 3 6 8前面）。

数据范围

n>0 ,
0≤m≤n ,
n+(n−m)≤25

输入样例：

5 3

输出样例：

思考题：如果要求使用非递归方法，该怎么做呢？

思路

思路一

状态压缩的dfs。枚举1~n的每个位置，使用还是不使用，当使用的个数sum达到m个，则输出当前结果，退出递归。若m减去当前使用的个数sum比剩下的课选位置的个数（即n-k）多，则继续枚举得不到m个数，退出递归。

思路二

对每个位置可放置的数进行枚举，每次枚举只能从比暂存数组a中当前位置k的前一个位置的数（及a[k-1]）大的数开始枚举。需进行剪枝，避免无用的递归。

题解

题解一

#include<iostream>
#include<cstdio>

using namespace std;

int n,m;

void dfs(int k,int sum, int state) {
    if(n-k < m-sum) return;
    if(sum == m) {
        for(int i = 0; i < n; i++) {
            if(state >> i & 1) printf("%d ",i+1);
        }
        puts("");
        return;
    }

    dfs(k+1, sum+1, state | (1 << k));   //使用第k位后再往下递归
    dfs(k+1, sum, state);                //不使用第k位后再往下递归
}

int main() {
    cin>>n>>m;
    dfs(0, 0, 0);

    return 0;
}

题解二

#include<iostream>
#include<cstdio>
using namespace std;

const int maxn = 20;
int n,m,a[maxn];

void combination(int k) {
    int p,q;
    for (p=a[k-1]+1; p<=n; p++) {   //从比前一个位置的元素大1的数进行选择（按字典序输出的特性）
        a[k]=p;

        if(n-p<m-k) return;     //剪枝，当剩余可选择的数的个数小于还未选够m个数的个数，则后面的递归没必要继续
        if (k<m) combination(k+1);
        else {
            for (q=1; q<=m; q++) printf("%d ",a[q]);
            printf("\n");
        }
    }
}

int main() {
    cin>>n>>m;
    if(m == 0) return 0;
    combination(1);

    return 0;
}

标题：	AcWing-93-组合
链接：	https://www.fightingok.cn/detail/31
更新：	2022-09-18 22:32:52
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可