Split into two equal halves
Splitting into equal halves is the same reachable-sum question, aimed at exactly half the total. About 10 minutes.
Splitting the bill fairly
Two friends want to split a pile of items so each gets exactly the same total value. Before any clever work, do a quick sanity check: add everything up. If the total is odd, an even split is impossible, full stop.
Say the items are worth 3, 4 and 6. The total is 13, and nobody can walk away with 6½ when every item is a whole number. No clever search needed: the answer is no.
22 is even, so it might split. Now the only question: can some subset reach 11? Start with just 0.
Find one half, and the other half is free
If the total is even, you only need to find items that add up to exactly half. Whatever is left over has to add up to the other half, because everything together is the total.
So "can this be split fairly?" turns into "can some items reach half the total?", which is the checklist from the last step. For 1, 5, 11 and 5 the total is 22, so aim for 11: the 11 on its own does it.
total = sum(nums)
if total % 2 == 1:
return False
half = total // 2
can = [True] + [False] * half
for x in nums:
for s in range(half, x - 1, -1):
if can[s - x]:
can[s] = True
return can[half]nums = [1, 2, 3, 5], total = 11. Can it be split into two equal-sum groups?
- ANo
- BYes
Show the answer
No. 11 is odd, so no split into two equal integer sums is possible.
Split into two equal halves
Given an array nums of positive integers, return true if it can be split into two groups (every number used exactly once, in one group or the other) whose sums are equal, or false otherwise.
nums = [1, 5, 11, 5] → true
1 ≤ nums.length ≤ 200 · 1 ≤ nums[i] ≤ 100