题目链接

算法竞赛进阶指南-5.递归实现指数型枚举

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

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

Method : 递归

你的疑惑是什么？

只用一个数组能输出多种结果么？ => 可以

#include <vector>
#include <iostream>

using namespace std;

int n;
vector<int> choosen;

void dfs(int depth) {
    // boundary
    if (depth == n + 1) {
        for (int i = 0; i < choosen.size(); i ++) {
            printf("%d ", choosen[i]);
        }
        cout << endl;
        return;
    }
    
    // 构造选或不选的递归二叉树
    choosen.emplace_back(depth);
    dfs(depth + 1);
    // recover
    choosen.pop_back();
    dfs(depth + 1);
}

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

复杂度分析

• 时间复杂度${O(nlog_2n)}$， 其中$log_2n$为递归函数栈的深度，外层$n$为打印数组的循环次数。

• 空间复杂度${O(n)}$， 数组${choosen}$的空间为${n}$，另外递归函数栈会花费额外常数级空间。

Method : 递归 + 位运算

使用位运算可以把choosen数组优化