Start learning free

LESSON 537 OF 679 · DYNAMIC PROGRAMMING

Partition Equal Subset Sum

Practice O(n · sum)

You get an array nums of positive integers.

Return true if you can split the numbers into two groups with the same sum. Otherwise, return false.

Every number goes into exactly one group. If a value appears twice, each copy can go into either group.

 

Example 1:

Input: nums = [3, 1, 4, 2, 2]
Output: true
Explanation: [4, 2] and [3, 1, 2] both add up to 6.
The two 2s are in different groups.

Example 2:

Input: nums = [4, 9, 2]
Output: false
Explanation: The total is 15, an odd number.
So it can't be split into two equal halves.

Example 3:

Input: nums = [1, 2, 5]
Output: false
Explanation: The total is 8, so each group needs 4.
1 + 2 is only 3, and 5 alone is too big.
2 + 2 would make 4, but there is only one 2.
So no group adds up to 4.

 

Constraints:

  • nums holds 1 to 200 numbers.
  • Each number is from 1 to 100.

Note:

Your algorithm should run in O(n · sum) time and use O(sum) extra space, where n is the number of values in nums and sum is their total.



If the total is odd, the answer is false. Otherwise the question becomes: can some of the numbers add up to exactly half, the total divided by 2? The other numbers then make the other half. Trying every group is far too slow: 200 numbers can be grouped in 2200 ways. Keep a table of booleans instead: can[s] says whether some of the numbers seen so far add up to s, for every s from 0 to half. Before any number is seen, only can[0] is true: no numbers at all make 0.

Add the numbers one at a time. For a number num, every sum that could be made before gives a new sum with num added: can[s] becomes true when can[s - num] is. Go over the sums from half down to num. Going down, can[s - num] is still the value from before this number, so each number is used at most once.
Why down, when Coin Change II goes up: in Coin Change II the loop over the sums goes up on purpose. There ways[a - coin] may already count the same coin, and that is how one coin value is used again and again. Here going up would reuse a number: on [1, 2, 5] it would make 4 as 1 + 1 + 1 + 1 or 2 + 2, and wrongly answer true for Example 3.

Each of the n numbers goes over at most half + 1 sums, with a constant amount of work for each: O(n · sum) time. The table holds half + 1 booleans: O(sum) space.
STEP 1 OF 9
    Ctrl + Enter to check