题目描述

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

输入格式

输入一个整数n。

输出格式

每行输出一种方案。

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

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

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

数据范围

1≤n≤15

输入样例：

3

输出样例：

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

题解：

可以很单纯的用STL中的vector枚举就行了，存在两种操作，要或不要。

#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> num;

void dfs(int k)
{
    //到达枚举边界，输出结果并结束
    if(k == n + 1)
    {
        for(int i = 0;i < num.size();++i)
            cout << num[i] << " ";

        cout << endl;
        return;
    }

    //不选择这个数
    dfs(k+1);

    //选择这个数
    num.push_back(k);
    dfs(k+1);
    //回溯
    num.pop_back();
}

int main(void)
{
    cin >> n;

    dfs(1);

    return 0;
}

当然也可以向yxc大神学习，用二进制状态压缩。也就是用二进制上的位来记录数有没有被用过。

#include <iostream>
using namespace std;

int n;

// u是当前枚举到的数，state是二进制数记录哪些数被选
void dfs(int u, int state) {
    if (u == n) {
        for (int i = 0; i < n; i++)
        {
            //判断第i位是不是1，即有没有被选，如果被选就输出
            if (state >> i & 1)
                //因为题目是从1开始的，所以要加1
                cout << i + 1 << " ";
        }

        cout << endl;
        return ;
    }

    //不用这个数，不进行操作
    dfs (u + 1, state);

    //用这个数，把第u位变成1
    dfs (u + 1, state | (1 << u));
}

int main(void) {

    cin >> n;

    dfs(0, 0);

    return 0;
}