AcWing 1573. 递归实现组合型枚举 II
原题链接
简单
作者:
hxj
,
2021-04-16 21:32:30
,
所有人可见
,
阅读 558
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;//从n个数中选m个数,列出所有情况(按字典序)
int a[100];
bool vis[100];
// dpt 树的深度,st开始的数
void dfs(int dpt, int st)
{
if(dpt == m)
{
for (int i = 0; i < n; i ++ ) {
if(vis[i]) {
printf("%d ", a[i]);
}
}
cout << endl;
return;
}
// 构建几个叉
for(int i = st; i < n; i++)
{
if(i != 0 && !vis[i-1] && a[i-1] == a[i]) continue;
vis[i] = true;
dfs(dpt+1, i+1);
vis[i] = false;
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) {
scanf("%d", &a[i]);
}
sort(a, a+n);//记得要排序啊
dfs(0, 0);
return 0;
}
if(i != 0 && !vis[i-1] && a[i-1] == a[i]) continue;哇,这是什么,看不懂啊
//树的这个位置不能走的条件,当前已经从树中出来(非根节点)并且它的前一个结点没有被走过并且当前有重复的时候就是回溯的条件
感觉是这个样,画个树自己看看每层怎么走?