वज़न बाँटना
आपको दिए गए n भार को दो समूहों में इस तरह विभाजित करना है कि इन समूहों के कुल भार का अंतर कम से कम हो।
इनपुट
इनपुट की पहली पंक्ति में एक अकेला पूर्णांक n (1 ≤ n ≤ 20) दिया होता है।
अगली पंक्ति में n स्पेस-सेपरेटेड पूर्णांक (1 ≤ ≤ ) दिए होते हैं।
आउटपुट
प्रोग्राम को इन दो समूहों के बीच का न्यूनतम संभव अंतर प्रिंट करना चाहिए।
उदाहरण
Input | इनपुट |
|---|---|
3 | 0 |
5 | 1 |
व्याख्या
पहले उदाहरण में, पहला समूह → 3, दूसरा समूह → 1 + 2 = 3, अतः दोनों समूहों का अंतर 0 है।
दूसरे उदाहरण में, पहला समूह → 1 + 7 = 8, दूसरा समूह → 2 + 3 + 4 = 9, जिसका अंतर 1 है।
Hint
आप सभी संभावित विभाजनों को आज़मा सकते हैं और फिर प्रत्येक विभाजन के लिए अंतर निकालकर देखें कि न्यूनतम अंतर कितना आता है।
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB