AcWing 1573. 递归实现组合型枚举 II
宋标 Lv5
  2022-08-18 02:31:22 2022-08-18 02:31    

题目

给定一个长度为 的可包含重复数字的序列，从中随机选取 个数字，输出所有可能的选择方案。

输入格式

第一行包含两个整数 。

第二行包含 个正整数。

输出格式

按照从小到大的顺序输出所有方案，每行 个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 5 7排在1 3 6 8前面）。

数据范围

,
,
,
序列内所有元素均不大于 。

输入样例：

5 3
1 2 2 3 3

输出样例：

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

题解

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
45
46
47
48
49
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30;

int n, m;
int a[N];
bool st[N];

void dfs(int u, int dx)
{
    if (dx > m) return;
    if (dx == m)
    {
        for (int i = 0; i < u; ++ i) 
            if (st[i])
                printf("%d ", a[i]);
        puts("");
        return;
    }
    if (u >= n) return;

    int k = u;
    while (k < n && a[k] == a[u]) st[k ++ ] = true, ++ dx;

    dfs(k, dx);

    for (int i = k - 1; i >= u; -- i)
    {
        st[i] = false;
        dfs(k, -- dx);
    }

}

int main()
{
    cin >> n >> m;
    for (int i = 0; i <= n; ++ i) cin >> a[i];

    sort(a, a + n);

    dfs(0, 0);

    return 0;
}
 评论