[揚鈞] 名天考程式

[yangmie (楊咩)]

好難

給大家有學c的看看我們去年考古題五題其中之一



To be Fair
Problem
Is it possible to split a set of numbers into two subsets, so that the sums
of these two subsets are equal? For example, consider a set {3, 4, 6, 2, 3}
then the answer is yes, since we can have two subsets {3, 4, 2} and {6, 3}
and the sums from both subsets are 9. However, it is impossible for us to do
that for the set {3, 4, 6, 2, 100}. Now write a program to determine if the
task is possible.
Input
The first line of the input is the number of input cases n. Each of the
following n lines is an input case. The first number of a line is the number
of numbers in an input case. Then the numbers for this input case follow.

Output
There are n lines of input. If an input case is possible, you need to output
"yes", otherwise output "no".

Sample Input
2
5 3 4 6 2 3
5 3 4 6 2 100


Sample Output
yes
no


Sample Input
1
20 2 2 4 8 16 32 64 128 256 512 1024 2048 5096 8192 16384 32768 65536 131072
262144 524288


Sample Output
yes


Hint
Hint: There is a simple way to figure this out. Consider the set {3, 4, 6, 2,
3}. We know that the task is to take some numbers out of this set so that the
sum is 9, since the sum of all numbers is 18. Now we have two choices: To
take the first 3 or not.

If we decided to take the first 3, the task would be to determine whether we
can take some numbers out of {4, 6, 2, 3}, and the sum of these number is 9 -
3 = 6.
If we decided not to take the first 3, the task would be to determine whether
we can take some numbers out of {4, 6, 2, 3}, and the sum of these number is
9 - 0 = 9. If either case is true then the original task can be done.
Otherwise it cannot be done.


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.240.42
推 Terrykho:經歷過計概,我才發現寫程式好難(計概班平均3X)
→ Terrykho:不過我們是先學JAVA,沒天份真的寫不出來
→ Terrykho:當然,我是屬於沒天份的
推 earowltanha:看起來很有趣 好想學學看
推 davidfu11:驚!樓上不是正在跟我打三國?
推 earowltanha:驚!樓上剛剛張飛被殺
推 earowltanha:問我為什麼在 ok啦 因為徐庶也被殺哈哈哈!!
推 smartchengyi:http://tw.youtube.com/watch?v=QX2-9fS5TBY
→ smartchengyi:這是台大資工錄的
推 yangmie:我認識原唱...是現在系籃隊長