开发者社区云计算文章正文

92. 递归实现指数型枚举

2024-05-24 36

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 92. 递归实现指数型枚举

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 18;
int n;
int vis[maxn]; // 选 or 不选
int a[maxn];
int f(int x)
{
     if (x == n)
     {
          for (int i = 1; i <= n; i++)
          {
               if (vis[i])
                    cout << a[i] << " ";
          }
          cout << endl;
          return 0;
     }
     else
     {
          vis[x + 1] = 1;
          f(x + 1);
          vis[x + 1] = 0;
          f(x + 1);
     }
}
int main()
{
     cin >> n;
     for (int i = 1; i <= n; i++)
     {
          a[i] = i;
     }
 
     f(0); // 从0开始
}

或者f(1)：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 18;
int n;
int vis[maxn]; // 选 or 不选
int a[maxn];
int f(int x)
{
     if (x > n)//f(1)开始，所以x > n 时结束
     {
          for (int i = 1; i <= n; i++)
          {
               if (vis[i])
                    cout << a[i] << " ";
          }
          cout << endl;
          return 0;
     }
     else
     {
          vis[x] = 1;//选
          f(x + 1);
          vis[x] = 0;//不选
          f(x + 1);
     }
}
int main()
{
     cin >> n;
     for (int i = 1; i <= n; i++)
     {
          a[i] = i;
     }
 
     f(1); // 从1开始
}