算法1 O(n * 2^n)
暴搜每个数选不选
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int a[N];
int n;
void dfs(int u, int cnt)
{
if(u == n + 1)
{
for(int i = 1; i <= cnt; i ++ )
cout << a[i] << ' ';
cout << endl;
return ;
}
dfs(u + 1,cnt);
a[++ cnt] = u;
dfs(u + 1, cnt);
}
int main()
{
cin >> n;
dfs(1, 0);
}
算法2 O(n * 2^n)
二进制枚举
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
for(int i = 0; i < 1 << n; i ++ )
{
for(int j = 0; j < n; j ++ )
if(i >> j & 1)
cout << j + 1 << ' ';
cout << endl;
}
}