题目描述

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

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

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

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

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

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

数据范围
1≤n≤15
输入样例：
3
输出样例：

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

正解

(暴力枚举)

首先看一眼题目，就知道这道题目必然是搜索也就是递归，那么怎么做呢，首先得有几个注意事项，第一点在每一次搜索完毕后，记得要递归，不然的话会出现很多重复不需要的答案，这是判重的一点。

第二点，搜索过程最重要的是，一定要确定好搜索的状态，我的代码比较啰嗦，大概是有三个状态，一个是当前最大的是那一个数字 x，第二个是当前搜索了几个数字了 now，m呢则是本次目标要搜索多少个数字

第三点，也就是特别容易忘记出错的，for循环内一定要是局部变量，不然的话如果是全局变量就会导致无法递归。

第三点：如果遇到错误的话，建议用静态查错，或者是自己模拟电脑主机，跑一遍程序，这样的话容易找到错误，尽量避免使用动态查错。

vis数组是标记数组，标记这个数字是否使用过，记得要处理好他的状态，不要忘记赋1，或者忘记重置清零。

C++ 代码

之前代码过于繁琐，已经简化修改 2019.1.18

位运算+递归深度优先搜索

#include <bits/stdc++.h>
using namespace std;
int n;
void dfs(int x,int now)
{
    if (x>n)
        return ;
    if (x==n)
    {
        for (int i=1;i<=n;i++)
            if (now>>(i-1) & 1)
               cout<<i<<" ";
        puts("");
    }
    dfs(x+1,now<<1 | 1);
    dfs(x+1,now<<1);
}
int main()
{
    cin>>n;
    dfs(0,0);
}

普通版

#include <bits/stdc++.h>
using namespace std;
int n,vis[110];
int p[110];
void dfs(int x,int now,int m)
{
    if (now==m)
    {
        for (int j=1;j<=p[0];j++)
            cout<<p[j]<<" ";
        cout<<endl;
        return ;
    }
    if (now+(n-x+1)<m)
        return ;
    for (int i=x+1;i<=n;i++)
        if (!vis[i])
        {
            vis[i]=1;
            p[++p[0]]=i;
            dfs(i,now+1,m);
            vis[i]=0;
            p[p[0]]=0;
            p[0]--;
            dfs(i,now,m);
            return ;
        }
    return ;
}
int main()
{
    cin>>n;
    puts("");
    for (int i=1;i<=n;i++)
    {
        dfs(0,0,i);
    }
    return 0;
}