Acwing 92.递归实现指数型枚举（递归与非递归）

Acwing 92.递归实现指数型枚举

• 目录
• • 题目描述
  • 算法1
  • • • 非递归做法
      • 时间复杂度
      • C++ 代码
  • 算法2
  • • • 递归做法
      • 时间复杂度
      • C++ 代码
  • 参考文献

目录 题目描述

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

输入格式： 输入一个整数 n。

输出格式 ：
1）每行输出一种方案。

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

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

4）各行（不同方案）之间的顺序任意。

数据范围 1≤n≤15
输入样例：
3
输出样例：
此处要输出空行
3
2
2 3
1
1 3
1 2
1 2 3

详细内容：原题链接

算法1 非递归做法

使用二进制表征状态，如n=3时，001代表3、2不选，只选1。

枚举所有二进制状态

时间复杂度

O ( n 2 ) O(n^2) O(n2)

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
//解法1：二进制枚举所有的选择状态输出
int n;
int st = 0;
int ed;
void printAns(int tp)
{
    for (int i = 1; i <= n; i++)
    {
        if (tp & 1)
        {
            cout << i << " ";
        }
        tp = tp >> 1;
        if (!tp)
            break;
    }
    cout << endl;
}

int main()
{
    cin >> n;
    ed = (1 << n) - 1;
    for (int i = st; i <= ed; i++)
    {
        if (!i)
            cout << endl;
        else
            printAns(i);
    }
    return 0;
}

---

算法2 递归做法

递归做法，参数值为不同层之间传输的信息，此处函数参数分别表示：
state—记录当前尝试的状态，同上述算法1的二进制表示方式
i—记录当前试到了第几个数位了

时间复杂度

O ( n 2 ) O(n^2) O(n2)

C++ 代码

#include <iostream>
using namespace std;
//解法2，递归+二进制记录状态
int n;
void print(int state)
{
    for (int i = 0; i <= n - 1; i++)
    {
        if ((state >> i) & 1)
            cout << i + 1 << " ";
    }
    cout << endl;
}

// dfs设计的时候考虑的是层之间需要传递的信息
// 状态信息state    i当前考虑到哪个了
void dfs(int i, int state)
{
    if (i > n) //搜到底了
    {
        print(state);
        return;
    }
    dfs(i + 1, state);                //不选该状态
    dfs(i + 1, state | (1 << i - 1)); // 1左移i位,表示选上该状态
}

int main()
{
    cin >> n;
    dfs(1, 0);
    return 0;
}

参考文献

[1] https://www.acwing.com/activity/content/code/content/19087/