Start learning free

LESSON 470 OF 569 · DYNAMIC PROGRAMMING

Partition Equal Subset Sum in JavaScript: O(n·sum) Dynamic Programming

Practice O(n · sum) Read the full explanation

Given an array of positive integers nums, return true if its numbers can be split into two groups with equal sums, or false otherwise.

Every number goes into exactly one of the two groups. Numbers that repeat in nums are separate numbers: each copy goes into one group.

 

Example 1:

Input: nums = [1, 5, 11, 5]
Output: true
Explanation: [1, 5, 5] and [11] both add up to 11.

Example 2:

Input: nums = [1, 2, 3, 5]
Output: false
Explanation: The total is 11. It is odd, 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 would have to add up to 4. But the numbers
can only make 1, 2, 3 (1 + 2), 5, 6 (1 + 5), 7 (2 + 5) and 8: never 4. Using the 1 four times
or the 2 twice would make 4, but each number can be used only once.

 

Constraints:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 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

    JAVASCRIPT · DYNAMIC PROGRAMMING

    Partition Equal Subset Sum in JavaScript, explained

    Problem overview

    canPartition(nums) receives an array of positive integers and returns true when the numbers can be split into two groups with equal sums, false otherwise. Every number goes into exactly one group, and repeated values are separate numbers: each copy goes into one group.

    For [1, 5, 11, 5] the answer is true: [1, 5, 5] and [11] both add up to 11. For [1, 2, 3, 5] the total is 11, which is odd, so no split is possible. For [1, 2, 5] the total is 8, so each group would need 4, but no choice of these numbers adds up to 4.

    Approach: a subset-sum table

    If the total is odd, the answer is false, because two equal halves always add up to an even number. Otherwise, let half be the total divided by 2. If some of the numbers add up to exactly half, the rest add up to the other half. So the question becomes: can some of the numbers make half?

    Trying every possible group is far too slow: 200 numbers can be grouped in 2^200 ways. Instead keep a table of booleans, can, where 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.

    Then add the numbers one at a time. For a number num, any sum s - num that could be made before gives the new sum s when num is added. So can[s] becomes true when can[s - num] is true.

    The order of the inner loop matters: it goes from half down to num. Going down, can[s - num] still holds its value from before this number was added, so each number is used at most once. Going up would read entries that already include num, letting a number be used again and again, which is the idea of a coin-change problem with unlimited coins, not of this one.

    Step by step

    1. Add everything up into total with nums.reduce((sum, num) => sum + num, 0). The 0 is the starting value.
    2. Reject an odd total: if total % 2 === 1, return false.
    3. Compute half as total / 2. The total is even here, so the division leaves nothing over.
    4. Create the table can with new Array(half + 1).fill(false). No sum above 0 can be made yet.
    5. Set can[0] = true. Every group grows from the empty one.
    6. Loop over the numbers with for (const num of nums). After each pass, can knows every sum the numbers so far can make, each used at most once.
    7. Loop over the sums downward: let s = half while s >= num, with s--. A sum below num can't contain it.
    8. Update the entry: can[s] = can[s] || can[s - num].
    9. Return can[half] after the outer loop.

    The solution in JavaScript

    class Solution {
    canPartition(nums) {
        const total = nums.reduce((sum, num) => sum + num, 0);
        if (total % 2 === 1) {
            return false;
        }
        const half = total / 2;
        const can = new Array(half + 1).fill(false);
        can[0] = true;
        for (const num of nums) {
            for (let s = half; s >= num; s--) {
                can[s] = can[s] || can[s - num];
            }
        }
        return can[half];
    }
}

    JavaScript details to watch:

    • reduce and its start value. The second argument, 0, is where the running sum starts. Without it, reduce on an empty array throws a TypeError, and the first element would serve as the start. Here the array is never empty, but the explicit 0 is a good habit.
    • % and negative numbers. In JavaScript the result of % takes the sign of the left operand, so -7 % 2 is -1 and the test === 1 would miss it. The lesson's numbers are positive, so the total is positive and the test is safe.
    • total / 2 is a real division. JavaScript has no separate integer type for this: 11 / 2 is 5.5. That is why the odd total is rejected first. Only then is half a whole number that can size an array.
    • new Array(n).fill(false) creates n empty slots and fills them. Without fill, the slots are empty rather than false.
    • || returns one of its operands. With booleans, can[s] || can[s - num] is true if either is. If can[s] is already true, the second part isn't even evaluated.

    Trace on [1, 5, 11, 5]

    The total is 22, so half is 11. This lists the sums s with can[s] true at the start and after each number:

    start:  0
after 1 : 0,1
after 5 : 0,1,5,6
after 11 : 0,1,5,6,11
after 5 : 0,1,5,6,10,11

    After the 11 is added, 11 is reachable (the number 11 alone), so the answer is true. The final 5 adds 10 (5 + 5), though the answer was already known.

    For [1, 2, 5], the total is 8 and half is 4:

    start:  0
after 1 : 0,1
after 2 : 0,1,2,3
after 5 : 0,1,2,3

    The 5 is bigger than half, so the inner loop doesn't run for it. The table never gets 4, and the answer is false.

    Complexity

    Time: O(n · sum), where n is the number of values in nums and sum is their total. Each of the n numbers goes over at most half + 1 sums, with a constant amount of work for each.

    Space: O(sum). The table holds half + 1 booleans.

    Edge cases and common mistakes

    • Looping upward. A version whose inner loop runs from num up to half answers true for [1, 2, 5], since it makes 4 as 1 + 1 + 1 + 1 or 2 + 2. It also answers true for [1, 5, 11, 5], which is correct, so that example doesn't reveal the bug; [1, 2, 5] does.
    • Odd total. [1, 2, 3, 5] returns false before the table is built.
    • A single number. [100] gives false: the total is even, but one number can't fill two groups. The table has half = 50 and the number is bigger, so nothing is added.
    • Two equal numbers. [1, 1] gives true.
    • A number bigger than half. It can't be part of a group that sums to half, and the loop condition s >= num skips it without an extra check. In [2, 2, 3, 5] the answer is false.
    • Largest inputs. 200 numbers equal to 100 give a total of 20000 and a table of 10001 entries. The function returns true, and with one of them changed to 99 the total is odd and it returns false.

    Testing

    • [1, 5, 11, 5] gives true.
    • [1, 2, 3, 5] gives false.
    • [1, 2, 5] gives false.
    • [100] gives false.
    • [1, 1] gives true.
    • [2, 2, 3, 5] gives false.
    • [3, 3, 3, 4, 5] gives true.
    • [1, 2, 3, 4, 5, 6, 7] gives true.
    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free