题目描述

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

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

输出格式
每行输出一种方案。

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

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

数据范围
1≤n≤15

样例

输入样例：
3
输出样例：

3
2
2 3
1
1 3
1 2
1 2 3

算法

(暴力枚举) $O(2^n)$

时间复杂度分析：对于没个数字有两种选择，选和不选

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

int n;
bool visited[15];

// 状态压缩 枚举
void f(int t){
    for(int i = 0; i < 1<<t; ++i){
        for(int j = 0; j < t; ++j){
            if(i >> j & 1){
                cout << (j + 1) << " ";
            }
        }
        cout << endl;
    }
}

// dfs 深度优先搜索
void solve(int t){
    if(t == n){
        for(int i = 0; i < n; ++i){
            if(visited[i]) cout << i+1 << " ";
        }
        cout << endl;
        return;
    }

    visited[t] = true;
    solve(t + 1);
    visited[t] = false;
    solve(t + 1);
}

int main(int argc, char const *argv[])
{
    cin >> n;
    // memset(visited, false, n);
    // solve(0);
    f(n);
    return 0;
}