606 . 零和問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

smgshabc123

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

41.7% (5/12)

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$ 個正整數 $x_i$，分別表示你可以選的數字。

  • $1 \le n \le 25$
  • $1 \le k, \sum_{i=0}^ {n-1}x_i \le 2^ {32}-1$，這行的意思是指所有 $x_i$ 加總以及 $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\le n\le 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