d115: 數字包牌

2019-08-27

內容

小涵是妳喜歡的人，可是她現在很無聊，她選了 n 個正整數給你玩，你要從這幾個數中選出 m 個號碼。

她說：如果你能輸出這些選出數字的所有可能，她才會喜歡妳噢。 (m<=n<=100)

PS.姓名純屬杜撰，如有雷同純屬巧合。

輸入

本題有多組測試資料。

每組測試資料有一行，第一個數 n，接下來有 n 個數 A1~An，這些數不會有重覆的，最後有一個數 m。

若 n=0 請結束程式，不必輸出任何資料。

3 6 2 5 2
5 5 2 3 9 12 2
0

輸出

你可以輸出:

1.”我一點都不喜歡妳!!” (不含雙引號) 她就會因為過度傷心而讓你得到 WA。

2.由小到大，依序列出從這 n 個數中選出 m 個號碼的所有可能 (請參考範例測資)。她就會因為過度開心而讓你得到 AC。全部可能輸出後請空一行。

2 5
2 6
5 6

2 3
2 5
2 9
2 12
3 5
3 9
3 12
5 9
5 12
9 12

解題思路

將讀入的數組排序好候用 dfs 遍歷指定長度的所有可能即可。

完整程式碼

AC (2ms, 92KB)

#include <stdio.h>
#include <stdlib.h>

int n, m, list[1000], output[1000];

int cmp(const int* lhs, const int* rhs)
{
    return *lhs - *rhs;
}

void dfs(int lv, int st)
{
    if (lv == m)
    {
        for (int i = 0; i < m; i++)
            printf("%d ", output[i]);
        putchar('\n');
        return;
    }
    for (int i = st; i < n; i++)
    {
        output[lv] = list[i];
        dfs(lv + 1, i + 1);
    }
}

int main()
{
    while (scanf(" %d", &n) == 1 && n)
    {
        for (int i = 0; i < n; i++)
            scanf(" %d", &list[i]);
        qsort(list, n, sizeof(int), cmp);
        scanf(" %d", &m);
        dfs(0, 0);
    }
    return 0;
}