Partition Equal Subset Sum

1. Define the problem

You are given an array of positive whole numbers. Return true if you can split them into two groups whose totals are exactly equal. Every number must go into one group or the other, and none can be split in half. If the whole array adds up to an odd total the answer is false right away, because an odd total cannot be halved evenly . Otherwise the real question is simpler than it looks: can some group of the numbers add up to exactly half the total ? If one group hits that number, the leftovers must hit it too.

Constraints

1 ≤ nums.length ≤ 200
1 ≤ nums_i ≤ 100
Every number must be placed in one of the two groups

Example

Inputnums = [1, 5, 3, 3]

Outputtrue

Explanation The numbers add up to 12, so each group needs 6. [1, 5] adds to 6 and [3, 3] adds to 6.

2. Know the words first

In plain terms

Subset: Any selection of the numbers, including none of them or all of them. The order you pick them in does not matter.
Target: Half of the total of all the numbers. That is the sum one group has to reach for the split to be even.
Reachable sum: A total you can build by adding up some of the numbers you have looked at so far, using each one at most once.

3. Visualize the solution

Tick off every sum you can build, up to half the total

Statusinit

Total is 12, so the target is 6. Only sum 0 is reachable so far.

What happens in this step

nums = [1, 5, 3, 3], total = 12
total is even, so target = 6

Every sum is marked F except 0, which is T. Picking no numbers always gives a total of zero.

Step 1 of 6

Steps to visualize

The numbers are [1, 5, 3, 3]; they add up to 12, so the target is 6.
The row is every sum from 0 to 6. T means that sum can be built, F means it cannot yet.
Sum 0 starts as T because picking nothing gives you zero.
Take the numbers one at a time.
For each number, a sum becomes reachable if the sum minus that number was already reachable.
Work from the biggest sum downwards so a number is never used twice in the same pass.
The answer is the mark on the target cell at the end.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Tick off every sum you can build, up to half the total

Statusinit

Total is 12, so the target is 6. Only sum 0 is reachable so far.

What happens in this step

nums = [1, 5, 3, 3], total = 12
total is even, so target = 6

Every sum is marked F except 0, which is T. Picking no numbers always gives a total of zero.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function canPartition(nums) {
  let total = 0;
  for (const num of nums) {
    total += num;
  }
  if (total % 2 !== 0) {
    return false;
  }

  const target = total / 2;
  const reachable = new Array(target + 1).fill(false);
  reachable[0] = true;

  for (const num of nums) {
    for (let sum = target; sum >= num; sum -= 1) {
      if (reachable[sum - num]) {
        reachable[sum] = true;
      }
    }
  }

  return reachable[target];
}

Time: O(n * total / 2)
Space: O(total / 2)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 5, 3, 3]`	`true`	example from the description
`nums = [1, 5, 11, 5]`	`true`	one large number balanced by several smaller ones
`nums = [1, 2, 3, 5]`	`false`	total is odd, so it can never be halved
`nums = [1, 1]`	`true`	smallest array that can be split
`nums = [1]`	`false`	one number cannot be shared between two groups
`nums = [2, 2, 3, 5]`	`false`	total is even but no group reaches exactly half

Partition Equal Subset Sum