Equal Split

The Idea

Splitting a set into two equal halves sounds like a search over subsets. It is really 0/1 knapsack with the values thrown away: mark sum zero as reachable, then let each number extend every sum already marked. If half the total lights up, the split exists. Backwards iteration keeps each number single-use.

Real-World Example

Two delivery vans and a pallet of crates that must be loaded to the same weight, or the depot scales reject the run. Nobody enumerates loadings. The loader tracks which total weights are still achievable and checks whether half the pallet is one of them.

The Code

nums = [3, 3, 4, 2]
total = sum(nums)
half = total // 2

can = [False] * (half + 1)
can[0] = True                        # the empty subset reaches zero
for n in nums:
    for s in range(half, n - 1, -1):   # backwards: each number used once
        can[s] = can[s] or can[s - n]

print(can)                                   # [True, False, True, True, True, True, True]
print(total % 2 == 0 and can[half])          # True — 3 + 3 against 4 + 2

can = [False] * 5
can[0] = True
for n in [1, 3]:
  for s in range(4, n - 1, -1):
      can[s] = can[s] or can[s - n]
print(can)