606 . 零和問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

smgshabc123

User's AC Ratio

90.9% (10/11)

Submission's AC Ratio

59.4% (19/32)

Tags

apcsc apcsc-recursion

Description

現在有 n 個正整數，請問你可不可以從中間選幾個數字使其加總為 k？
如果可以輸出 YES，否則輸出 NO。（數字不能重複選擇。）

舉例來說，如果有五個數字，分別是 [3, 7, 11, 9, 4]：

  • 如果目標 k 為 16，則要輸出 YES，因為 9+7=16。
  • 如果目標 k 為 17，則要輸出 NO，因為不管怎麼選擇都無法讓加總變成 17。

官方小小提示

  • 如果現在可以選五個數字，分別是 [3, 7, 11, 9, 4]（也就跟上面的舉例一樣），那麼遞迴樹大概會長的像下面這張圖一樣，你可以用這張圖去思考你的遞迴該怎麼實作。
大致的遞迴樹長相

Input Format

一開始輸入一行，其有兩個正整數 n,k 以一個空格間隔，分別代表你有幾個數字可以選擇，以及題目所給定的目標 k。

接下來會在輸入一行，這行有 n 個正整數 xi，分別表示你可以選的數字。

  • 1≤n≤25
  • 1≤k,∑i=0n−1xi≤232−1，這行的意思是指所有 xi 加總以及 k 都不會超過 int 的大小。

Output Format

輸出一行 YES 或 NO，表示目標 k 可不可以從題目所給的 n 個數字中選幾個數字使其加總為 k。

Sample Input 1

5 16
3 7 11 9 4

Sample Output 1

YES

Sample Input 2

5 17
3 7 11 9 4

Sample Output 2

NO

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~7 1≤n≤5 30
3 0~16 無額外限制 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3
1 1000 524288 65536 1 2 3
2 1000 524288 65536 2 3
3 1000 524288 65536 2 3
4 1000 524288 65536 2 3
5 1000 524288 65536 2 3
6 1000 524288 65536 2 3
7 1000 524288 65536 2 3
8 1000 524288 65536 3
9 1000 524288 65536 3
10 1000 524288 65536 3
11 1000 524288 65536 3
12 1000 524288 65536 3
13 1000 524288 65536 3
14 1000 524288 65536 3
15 1000 524288 65536 3
16 1000 524288 65536 3
Submit
Back to Top