递归实现指数型枚举

92. 递归实现指数型枚举 - AcWing题库

题目描述

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1≤n≤15

解题思路

1.状态压缩解法

n的范围很小，我们考虑使用状态压缩，最多15位，依次代表数字1~15，如果这个数出现，就为1，否则为0。

那么所有的状态就是2^{15}=32768种。

时间复杂度 O（2^n）

 #include <bits/stdc++.h>
 #define INF 0x3f3f3f3f
 using namespace std;
 typedef long long LL;
 const int N = 1e5 + 5;
 int n;
 int main()
 {
     scanf("%d", &n);
     int all = 1 << n;
     for (int i = 0; i < all; i++)
     {
         int t = i, val = 1;
         while (t)
         {
             if (t & 1)
             {
                 printf("%d ", val);
             }
             t >>= 1;
             val++;
         }
         printf("\n");
     }
 }

2.递归

列举出所有情况即可，从1开始选，要么选上，要么不选，每个数都是两种情况，时间复杂度O(2^n);

 #include <bits/stdc++.h>
 #define INF 0x3f3f3f3f
 using namespace std;
 typedef long long LL;
 const int N = 1e5 + 5;
 int n;
 vector<int>vt;
 ​
 void dfs(int p)
 {
     if(p==n+1)
     {
         for(auto i:vt)
         {
             printf("%d ",i);
         }
         printf("\n");
         return ;
     }
     dfs(p+1);   //不选p
     
     //选p
     vt.push_back(p);
     dfs(p+1);
     vt.pop_back();
 }
 ​
 int main()
 {
     scanf("%d", &n);
     dfs(1);
 }