題目連結:
題目大意:
給定三正整數 n 、 k 、 target (1 ≦ n ≦ 20 , 1 ≦ k ≦ n ,0 ≦ target ≦ 2 × 10 ^ 7),代表有 n 個錢袋,要從中挑出 k 個使得總金額恰好為 target 。
接著有 n 個正整數 i (0 ≦ i ≦ 10 ^ 6),代表其中一個錢袋內含的金額。
若可以從 n 個錢袋中挑出 k 個使得總金額剛好為 target ,則輸出「YES」;反之,輸出「NO」。
5 2 3
1 2 3 4 5
5 3 3
1 2 3 4 5
5 4 10
1 2 3 4 5
5 1 0
1 2 3 4 5
與
這題類似,但是只能從中挑 k 個。因此深度優先搜尋(DFS)的遞迴停止條件要多判斷現在挑了幾個錢袋。如果挑了 k 個以上,則回到上一層的遞迴堆疊。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。