606 . 零和問題
TopCoder
Tags
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
3 7 11 9 4
Sample Output 1
YES
Sample Input 2
5 17
3 7 11 9 4
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 |