题目
给定一个长度为 的可包含重复数字的序列，从中随机选取任意多个数字，输出所有可能的选择方案。
输入格式
第一行包含一个整数 ，表示序列长度。
第二行包含 个正整数。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
数据范围
,
序列内所有元素均不大于 。
输入样例：
3
1 2 2
输出样例：
1
2
1 2
2 2
1 2 2
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
int n;
int a[N];
bool st[N];
void dfs(int u)
{
if (u == n)
{
for (int i = 0; i < n; ++ i)
if (st[i]) printf("%d ", a[i]);
puts("");
return;
}
int k = u + 1;
while (k < n && a[k] == a[u]) ++ k;
dfs(k);
for (int i = u; i < k; ++ i)
{
st[i] = true;
dfs(k);
}
for (int i = u; i < k; ++ i) st[i] = false;
}
int main()
{
cin >> n;
for (int i = 0; i < n; ++ i) cin >> a[i];
sort(a, a + n);
dfs(0);
return 0;
}
|
