SPOJ Problem Set (zestaw4) 4239. Równy Podział Zbioru Problem code: SETPART

Danych jest n < 20 liczb: x 1 , x 2 , ..., x n , każda ze zbioru {1, 2,...,20}. Niech S= x 1 + x 2

+ ... + x n jest ich sumą. Sprawdź, czy da się wybrać spośród tych n liczb podzbiór, którego suma jest równa dokładnie S/2.

Wejście

Najpierw t < 500 liczba zbiorów. Następnie dla każdego zbioru najpierw n, a następnie n liczb.

Wyjście

Dla każdego zbioru w osobnym wierszu jedno słowo: YES jeśli da się otrzymać połowę sumy albo słowo NO jeśli nie jest to możliwe.

Przykład Wejście: 4

3

2 1 3

3

11 10 9

4

1 2 1 6

5

11 1 2 10 18

Wyście:

YES

NO

NO

YES

Komentarz: 1: 2 + 1 = 3

2: brak rozwiązania 3: brak rozwiązania 4: 11 + 10 = 1 + 2 + 18

Added by:

Łukasz Kuszner Date:

2009-04-20

Time limit: 2s Source limit:50000B

Languages: All except: TECS

Resource:

folklor

1