Problem:


ビーカー

いろいろな容量のビーカーが与えられています。はじめに、その中の一番容量の大きなビーカーを一個選び、蛇口から水をいっぱいになるまで注ぎます。つぎに、次のルールにしたがいながら、ビーカーの水を他のビーカーに移し替えていきます。

ビーカーに入っている水は,残さずにすべて他のビーカーに移さなければならない。ただし、一個のビーカーに水を全部移せないときは、複数のビーカーに分けて移してもよい。

ビーカーに水を入れるとき、いっぱいになるまで水を注がなければならない。また、水をこぼしてはならない。

複数のビーカーから同じビーカーに一度に水を注いではならない。

同じビーカーには一度しか水を注いではならない。

このルールにしたがったとき、ビーカーの個数 n と各ビーカーの容量を入力とし、すべてのビーカーに水を注ぐことができるかどうかを判定して出力するプログラムを作成してください。すべてのビーカーに水を注ぐことができるときは YES (半角英大文字)、できないときは NO (半角英大文字) を出力してください。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。各データセットは以下の形式で与えられます。

n
c1 c2 ... cn

1 行目にビーカーの個数 n (1 ≤ n ≤ 50) が与えられます。２行目に i 番目のビーカーの容量を表す整数 ci (1 ≤ ci ≤ 100) が与えられます。

データセットの数は 105 を超えません。

Output

データセット毎に判定結果を１行に出力します。

Sample Input

10
11 2 23 4 2 12 8 5 2 10
8
2 1 3 11 2 3 1 4
9
5 9 1 2 4 8 17 1 8
8
3 38 9 4 18 14 19 5
1
1
0

Output for the Sample Input

YES
YES
YES
NO
YES



Sample input:
10
11 2 23 4 2 12 8 5 2 10
8
2 1 3 11 2 3 1 4
9
5 9 1 2 4 8 17 1 8
8
3 38 9 4 18 14 19 5
1
1
0


Sample output:
YES
YES
YES
NO
YES

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = int(input())
    if n == 0: break
    beakers = list(map(int, input().split()))
    m = max(beakers)
    beakers.remove(m)
    beakers.sort()
    if beakers:
        beakersum = [beakers[0]]
        del beakers[0]
    else:
        print("YES")
        continue

    if sum(beakers) < m:
        print("NO")
        continue
    elif sum(beakers) == m:
        print("YES")
        continue

    for b in beakers:
        tmp = [bks + b for bks in beakersum if bks + b <= m]
        beakersum.extend(tmp)
        if m in beakersum:
            break
    
    if m in beakersum:
        print("YES")
    else:
        print("NO")

Submission status: Memory Limit Exceeded

Solution code:
while True:
    n = int(input())
    if n == 0: break
    beakers = list(map(int, input().split()))
    m = max(beakers)
    beakers.remove(m)
    beakers.sort()
    if beakers:
        beakersum = [beakers[0]]
        del beakers[0]
    else:
        print("YES")
        continue
    for b in beakers:
        tmp = [bks + b for bks in beakersum]
        beakersum.extend(tmp)
    
    if m in beakersum:
        print("YES")
    else:
        print("NO")