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

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。

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

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

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

数据范围 1≤n≤15

输入样例:

3

输出样例:

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

题目分析

DFS 即可

代码实现

#include <iostream>
using namespace std;

int n, idx, ans[20], st;
void dfs(int st, int maxnum) {
    for(int i = 0; i < idx; ++i) cout << ans[i] << ' '; cout << '\n';
    for(int i = 1; i <= n; ++i) {
        if(st & (1 << i) || i < maxnum) continue;
        ans[idx++] = i;
        dfs(st + (1 << i), max(maxnum, i));
        --idx;
    }
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    dfs(0, -1);
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status