AcWing 1573. 递归实现组合型枚举 II
原题链接
简单
作者:
我要出去乱说
,
2021-02-07 12:45:30
,
所有人可见
,
阅读 976
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30;
int n, m;
int a[N];
bool st[N];
void dfs(int u, int s)
{
if (s > m) return; //跳过重复数字时累加的s可能会大于m,为无效方案
if (s == m) //选择个数恰好等于m时输出方案
{
for (int i = 0; i < n; i ++ )
if (st[i])
cout << a[i] << ' ';
cout << endl;
return;
}
if (u == n) return; //已经遍历了所有数,返回
int k = u;
while (k < n && a[k] == a[u]) st[k ++ ] = true, s ++ ; //先把最小的输出,拉满
dfs(k, s);
for (int i = k - 1; i >= u; i -- ) //倒过来恢复现场
{
st[i] = false;
s -- ;
dfs(k, s);
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> a[i];
sort(a, a + n); //可重复枚举都要先排序
dfs(0, 0); //初始状态:从前0个数中选0个数
return 0;
}
你好,我感觉我思路和你是一样的楼主,但是我这个没输出,我看了半天,不知道为什么,大佬能不能帮我看看