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