Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Có ~n~ quả táo với trọng lượng đã biết. Nhiệm vụ của bạn là chia các quả táo thành hai nhóm sao cho độ chênh lệch giữa tổng trọng lượng của hai nhóm là nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~n~: số quả táo.
• Dòng tiếp theo chứa ~n~ số nguyên ~p_1, p_2, \ldots, p_n~: trọng lượng của từng quả táo.

Kết quả

• In ra một số nguyên: độ chênh lệch nhỏ nhất giữa tổng trọng lượng của hai nhóm.

Giới hạn

• ~1 \le n \le 20~.
• ~1 \le p_i \le 10^9~.

Sample Input 1

5
3 2 7 4 1

Sample Output 1

1

Giải thích

Nhóm 1 gồm các quả nặng 2, 3 và 4 (tổng 9), nhóm 2 gồm các quả nặng 1 và 7 (tổng 8).

Nguồn: CSES Problem Set – 1623.