Có \(n\) quả táo với trọng lượng đã biết. Hãy chia các quả táo thành hai nhóm sao cho sự chênh lệch về trọng lượng giữa hai nhóm là nhỏ nhất.

INPUT FORMAT

Dòng đầu tiên của đầu vào có một số nguyên \(n\) : số lượng quả táo.
Dòng tiếp theo có có \(n\) số nguyên \(P_1, P_2, P_3...P_N\): trọng lượng của mỗi quả táo.

OUTPUT FORMAT

Hãy in ra một số nguyên: chênh lệch nhỏ nhất giữa trọng lượng của hai nhóm

RẰNG BUỘC

\(1 \leq n \leq 20\)
\(1 \leq P_i \leq 10^9\)

Ví dụ:

Input

5
3 2 7 4 1

Output

1

Giải thích: Nhóm 1 có trọng lượng 2, 3 và 4 (tổng trọng lượng 9), nhóm 2 có trọng lượng 1 và 7 (tổng trọng lượng 8)

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House