DSA Factory
Free Recursion lessonsRecursion · Stage 3 · Include or skip · Step 4

Two piles as even as possible

Split values into two piles with the smallest difference by sending each value to one pile or the other and tracking the difference. About 14 minutes.

Left pile or right pile

Two friends split a pile of coins and want the totals as equal as possible. For each coin there are two choices: it goes to the first friend or the second. After all choices, the difference between the two totals is what matters.

Rather than keeping both totals, keep their difference. A coin given to the first friend raises the difference by its value. A coin given to the second lowers it. Start at 0 and try both for every coin.

First friend: gap goes up by the value.
Second friend: gap goes down by the value.
In code
def signs(i, total):
    if i == len(nums):
        return 1 if total == 0 else 0
    plus = signs(i + 1, total + nums[i])
    minus = signs(i + 1, total - nums[i])
    return plus + minus
Split 5, 2, 3, 6 into two piles.
5
0
2
1
3
2
6
3
leftright

Start with a gap of 0. Give 5 to the first friend: the gap is 5.

Move 1 of 5

Absolute value at the end

A gap of minus 3 is as good as plus 3, since it just means the other friend has more. So at the end return the absolute value, and take the smallest over every way of splitting.

You can halve the work by always giving the first coin to the first friend, since swapping the friends gives the mirror image. That is an optional improvement. The simple version already works for about 20 values.

At the end: return the absolute value of the gap.
Keep the best: the smaller of the two branches.
Quick check

At the end of one path the gap is −4. What does that path contribute to the answer?

  1. A4, the absolute value
  2. B−4
  3. C0
Show the answer

4, the absolute value. The size of the gap is what matters, not which friend has more.

Your problem

Two piles

nums is a list of non-negative whole numbers. Divide them into two piles (every value goes into exactly one pile; a pile may be empty) so that the totals of the two piles are as close as possible. Return the smallest possible difference between the two totals.

Example
nums = [3, 1, 4, 2] → 0

0 ≤ length ≤ 18 · 0 ≤ value ≤ 1,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve