ETH官方钱包

前往
大廳
主題

ZeroJudge - d115: 數字包牌 解題心得

Not In My Back Yard | 2021-08-01 00:00:12 | 巴幣 0 | 人氣 341

題目連結:


題目大意:
輸入有多列(以一列「0」作結),每列為一筆測試資料。每列開頭給定一正整數 n,緊接著有 n 個正整數(這些數字彼此相異),最後再給定一整數 m(m ≦ n ≦ 100)。

請將從這 n 個整數挑出 m 個數字的方法全數列舉出來,並按照字典序由小到大輸出。每列的輸出為一組挑選的方法。每筆測資之輸出結束後,再輸出一列空白列(參見範例輸出入)。



範例輸入:
3 6 2 5 2
5 5 2 3 9 12 2
0


範例輸出:
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



解題思維:
就跟其他的窮舉問題一樣利用深度優先搜尋(Depth First Search,DFS)來窮舉即可(如這題)。

而因為我們需要輸出時是按照字典序的,因此我們預先將給定的 n 個數字按照大小由小到大排列。然後我們從小的數字開始挑,每次遞迴只往上一次挑的數字後面(也就是右邊)的數字去跑。這樣既不會挑到重複的挑法,也可以讓輸出時按照字典序去輸出。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作