Partition Equal Subset Sum

The problem

Given a list of positive whole numbers nums, return true if the numbers can be divided into two groups whose sums are equal, and false if they cannot. Every number must go into exactly one of the two groups, and the groups do not have to be the same size. Equal values at different positions are separate numbers. A list with a single number can never be divided this way, so its answer is false.

What to write

function solve(nums: number[]): boolean

Input
nums = [1,5,11,5]

Output
true

Input
nums = [1,2,3,5]

Output
false

Constraints

nums is nonempty and contains positive integers.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Add up the whole list. The two groups share that total equally, and every number is whole, so an odd total can never work. With an even total, you know exactly what each group has to add up to.

2. Hint 2: Ask a smaller question

   Take the numbers 1 and 5 and write down every sum that a group of them can make, counting the empty group. Now a third number, 11, joins. How does your list of sums change? Did you have to start again from nothing?

3. Hint 3: Name the pattern

   The question is whether some group adds up to exactly half the total, with each number in the group or out of it. Items to choose and an exact total to reach are the signal for knapsack dynamic programming: one entry for every total up to the target, updated as each item is taken. Read the lesson on knapsack dynamic programming.

4. Hint 4: State the invariant

   The table has one mark for every sum from 0 to half the total. After some of the numbers have been taken, a mark is true exactly when some group of those numbers adds up to that sum, each number used at most once. The empty group gives the sum 0.

5. Hint 5: Sketch the pseudocode

   If the total is odd, return false. target = total / 2. reach[0] = true, every other mark false. For each number x: for sum from target down to x: if reach[sum - x] is true, set reach[sum] = true. Return reach[target].

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Reduce the task to subset sum at half the total. Update reachable sums downward so each number is used at most once.

The slow way

Try every group: each number is either in it or out, and you compare the sum of the group with the sum of the rest. It is correct, but every extra number doubles the count. 4 numbers have 16 groups, and 20 numbers have 1,048,576.

The insight

Two equal groups each add up to half the total, so it is enough to ask whether some group reaches that half. Many different groups share the same sum, and only the sum matters. So instead of groups, keep track of which sums can be reached, and let each new number add to them.

Step by step

1. Add up the numbers: an odd total cannot be split into equal halves. Two equal groups would each need half of the total. With whole numbers an odd total has no such half, so the answer is false right away.
2. Each group must add up to half the total: call that the target. If one group reaches the target, the numbers left over add up to the other half by themselves. So the question becomes whether some group adds up to the target.
3. Make a mark for every sum from 0 to the target: only 0 is reachable. A mark says whether some group of the numbers taken so far adds up to that sum. Before any number is taken, only the empty group exists, and its sum is 0.
4. Take the numbers one at a time. After each number the marks cover every group that can be made from the numbers taken so far, with each number used at most once.
5. Go through the sums from the target down to the number itself. Each mark is worked out from the mark of a smaller sum. Going downward, that smaller mark has not been touched yet for this number, so the number is never counted twice. Sums below the number cannot contain it.
6. Mark a sum if the sum minus this number is already marked. A group that reaches the smaller sum can take this number and reach this sum. A sum that was marked before stays marked, because the number can also be left out.
7. Return the mark of the target. The mark of the target is true exactly when some group of all the numbers adds up to half the total, and the rest then forms the other half.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Add up the numbers: an odd total cannot be split into equal halves
  const sum = nums.reduce((a, b) => a + b, 0);
  if (sum % 2) return false;
  // 2. Each group must add up to half the total: call that the target
  const target = sum / 2;
  // 3. Make a mark for every sum from 0 to the target: only 0 is reachable
  const dp = Array(target + 1).fill(false);
  dp[0] = true;
  // 4. Take the numbers one at a time
  for (const n of nums) {
    // 5. Go through the sums from the target down to the number itself
    for (let s = target; s >= n; s--) {
      // 6. Mark a sum if the sum minus this number is already marked
      dp[s] = dp[s] || dp[s - n];
    }
  }
  // 7. Return the mark of the target
  return dp[target];
}

function solve(nums: number[]): boolean {
  // 1. Add up the numbers: an odd total cannot be split into equal halves
  const sum = nums.reduce((a, b) => a + b, 0);
  if (sum % 2) return false;
  // 2. Each group must add up to half the total: call that the target
  const target = sum / 2;
  // 3. Make a mark for every sum from 0 to the target: only 0 is reachable
  const dp = Array(target + 1).fill(false);
  dp[0] = true;
  // 4. Take the numbers one at a time
  for (const n of nums) {
    // 5. Go through the sums from the target down to the number itself
    for (let s = target; s >= n; s--) {
      // 6. Mark a sum if the sum minus this number is already marked
      dp[s] = dp[s] || dp[s - n];
    }
  }
  // 7. Return the mark of the target
  return dp[target];
}

def solve(nums):
    # 1. Add up the numbers: an odd total cannot be split into equal halves
    total = sum(nums)
    if total % 2:
        return False
    # 2. Each group must add up to half the total: call that the target
    target = total // 2
    # 3. Make a mark for every sum from 0 to the target: only 0 is reachable
    dp = [False] * (target + 1)
    dp[0] = True
    # 4. Take the numbers one at a time
    for num in nums:
        # 5. Go through the sums from the target down to the number itself
        for subtotal in range(target, num - 1, -1):
            # 6. Mark a sum if the sum minus this number is already marked
            dp[subtotal] = dp[subtotal] or dp[subtotal - num]
    # 7. Return the mark of the target
    return dp[target]

Example 1, traced

Input
nums = [1,5,11,5]

Output
true

Why it works

After each number, a sum is marked exactly when some group of the numbers taken so far adds up to it, with each number used at most once. A new number adds itself to every sum that was reachable without it, and removes nothing. At the end the mark of the target says whether half the total can be reached.

Time and space

Time O(n · sum), extra space O(sum). There is one mark per sum from 0 to half the total, which is the O(sum) space. Each of the n numbers walks down that table once, so the time is n times the size of the table, O(n · sum).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Walking the sums upward. A freshly marked sum is then extended by the same number again. For 2, 2, 3, 5 the first 2 alone marks 2, 4 and 6, and the answer is true instead of false.
• Giving each number, largest first, to the group with the smaller sum. For 3, 3, 2, 2, 2 that ends with groups of 7 and 5, although 3, 3 and 2, 2, 2 both add up to 6.
• Skipping the check for an odd total and rounding the half down. For 1, 2, 3, 5 the total is 11, the rounded half is 5, and 5 can be reached, so the answer is true instead of false.

Pattern

Knapsack dynamic programming. Builds on Coin Change.

Keep going