重りを分ける
与えられた n 個の重り を、2つのグループに分割して、それぞれの合計の差が最小になるようにしてください。
入力
入力の最初の行には、1 つの整数 n (1 ≤ n ≤ 20) が与えられます。
次の行には、n 個の整数 (1 ≤ ≤ ) が空白区切りで与えられます。
出力
2つのグループの差のうち、可能な限り小さい値を出力してください。
例
入力 | 出力 |
|---|---|
3 | 0 |
5 | 1 |
解説
最初のグループ → 3、もう一方のグループ → 1 + 2 = 3
最初のグループ → 1 + 7 = 8、もう一方のグループ → 2 + 3 + 4 = 9
ヒント
すべての 通りの分け方を試して、それぞれのグループ差を求めれば、最小となる差を見つけることができます。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB