Loading...
Loading...
Loading...
Rahul and Priya bought n boxes of laddoos for their hostel floor. Box i holds a_i laddoos. They want to share the boxes so that each of them carries exactly the same number of laddoos.
Every box goes whole to one of them; nobody opens a box. Print YES if such a split exists, and NO otherwise.
YES or NO.Example 1
Input
4 3 1 4 2
Output
YES
Rahul takes 3 and 2, Priya takes 1 and 4. Both carry 5.
Example 2
Input
3 2 3 7
Output
NO
The total is 12, so each needs 6. No group of boxes adds up to 6.
Try the problem first. Open one hint at a time.
If the total is odd, the answer is NO. Otherwise one person needs exactly half of the total.
So the real question is: can some group of boxes add up to exactly half?
Keep a table can[s]: is the sum s reachable with the boxes seen so far? Before any box, only can[0] is true.
For each box of size a, a sum s becomes reachable if s - a was reachable before this box. Go through s from high to low so each box is used once.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor