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

输入格式

输入一个整数 n

输出格式

每行输出一种方案。 同一行内的数必须升序排列,相邻两个数用恰好 1 个空格隔开。 对于没有选任何数的方案,输出空行。

数据范围

1 ≤ n ≤ 15

输入样例

3

输出样例

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

题目分析

DFS

代码实现

#include <iostream>
#include <bitset>
#include <vector>
using namespace std;
const int N = 20;

int n;
vector <int> ans;
bitset <N> bt;
void dfs(int pre) {
    for (auto& i : ans) cout << i << ' ';
    cout << '\n';
    for (int i = pre + 1; i <= n; ++i) {
        if (!bt[i]) {
            bt[i] = 1;
            ans.push_back(i);
            dfs(i);
            ans.erase(ans.end() - 1);
            bt[i] = 0;
        }
    }
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    dfs(0);
    return 0;
} 
分类: Recursion

0 条评论

发表回复

Avatar placeholder

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

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

站点状态:Status