AcWing 1572. 递归实现指数型枚举 II
原题链接
简单
作者:
我要出去乱说
,
2021-02-07 10:51:54
,
所有人可见
,
阅读 587
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int n;
int a[N];
bool st[N];
void dfs(int u) //u表示的不是第几段,而是每段开头的第一个数,后面的数会跳过
{
if (u == n) //到达叶子节点,输出该方案
{
for (int i = 0; i < n; i ++ )
if (st[i])
cout << a[i] << ' ';
cout << endl;
return;
}
int k = u;
while (k < n && a[k] == a[u]) k ++ ; //跳过同一段后面的数字
dfs(k); //没有标记st直接dfs,即枚举选0个的情况
for (int i = u; i < k; i ++ ) //将同一段的数逐个设为true然后dfs
{
st[i] = true;
dfs(k); //从下一段开始枚举
}
for (int i = u; i < k; i ++ ) st[i] = false; //批量还原现场
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];
sort(a, a + n);
dfs(0);
return 0;
}
批量还原现场和上面写成一个循环不行吗
太久远了我一时也想不起来了,不过可以试试