Start learning free

LESSON 474 OF 573 · DYNAMIC PROGRAMMING

Partition Equal Subset Sum in Go: 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 11
    Ctrl + Enter to check

    GO · DYNAMIC PROGRAMMING

    Partition Equal Subset Sum in Go, explained

    Problem overview

    The function canPartition receives a slice nums of positive integers and returns true if the numbers can be split into two groups with equal sums, and false otherwise. Every number goes into exactly one group. Repeated values are separate numbers, and 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] it is false, because the total is 11, which is odd and can't be split into two equal halves. For [1, 2, 5] it is also false: the total is 8, so each group would need 4, but the numbers can only make 1, 2, 3, 5, 6, 7 and 8. Using the 1 four times or the 2 twice would make 4, but each number can be used only once.

    The statement asks for O(n · sum) time and O(sum) extra space, where n is the number of values and sum is their total.

    Approach: can some of the numbers make half the total?

    If the total is odd, the answer is false straight away. 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 exactly half?

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

    Then add the numbers one at a time. For a number num, any sum that could be made before gives a new sum with num added, so can[s] becomes true when can[s - num] is true. The loop over the sums goes from half down to num. Going down, can[s - num] still holds its value from before this number, so each number is used at most once. A loop that went up would reuse the same number in one pass, as in coin problems where a coin can be used again and again.

    The table on the first example

    For [1, 5, 11, 5] the total is 22 and half is 11. Printing the sums marked true after each number gives:

    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]

    The last list contains 11, so the answer is true. 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 list never contains 4, so the answer is false. The 5 is bigger than half, so it can't change the table.

    Step by step

    1. Add up the numbers. Start total at 0 and add each num in a range loop.
    2. Reject an odd total. If total%2 == 1, return false: two equal halves always add up to an even number.
    3. Compute half as total / 2.
    4. Create can with make([]bool, half+1). Every entry starts as false, and the extra place holds the sum half itself.
    5. Set can[0] = true. Every sum grows from the empty group.
    6. Loop over nums again. After a number is handled, can knows every sum the numbers so far can make, each one used at most once.
    7. Loop over the sums downward: s from half while s >= num. A sum below num can't contain it.
    8. Update the table: can[s] = can[s] || can[s-num]. If the earlier numbers can make s - num, adding num makes s.
    9. Return can[half].

    The solution in Go

    func canPartition(nums []int) bool {
    total := 0
    for _, num := range nums {
        total += num
    }
    if total%2 == 1 {
        return false
    }
    half := total / 2
    can := make([]bool, half+1)
    can[0] = true
    for _, num := range nums {
        for s := half; s >= num; s-- {
            can[s] = can[s] || can[s-num]
        }
    }
    return can[half]
}

    The Go details worth a closer look:

    • range and the blank identifier. for _, num := range nums yields an index and a value. Go refuses to compile an unused variable, so the index is dropped with _.
    • make for a slice of bools. make([]bool, half+1) creates half+1 elements, all false, which is the zero value of bool.
    • || short-circuits. If can[s] is already true, the right side is not evaluated. The result is the same either way, because both sides are plain reads.
    • Integer division. total / 2 truncates, and total%2 is the remainder. With the odd total ruled out first, half is exact. For an odd total such as 11, 11 / 2 is 5 and 11 % 2 is 1.
    • A loop that may not run. If num is larger than half, the condition s >= num is false at once, so the inner loop does nothing and the index s-num is never negative.

    Complexity

    Time: O(n · sum). Each of the n numbers goes over at most half + 1 sums, with a constant amount of work for each one.

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

    Edge cases and common mistakes

    • Odd total. [1] and [1, 2, 3, 5] return false before any table is built.
    • A single number. [2] has an even total, but the half is 1 and no number makes it, so the answer is false.
    • Equal pairs. [3, 3] and [1, 1] return true, since each copy goes into one group.
    • One number is too big. [1, 1, 6] has a total of 8 and a half of 4. The 6 can't fit in a group of 4, and the answer is false. The same happens for [100, 1, 1, 1, 1].
    • Looping upward. If the inner loop runs for s := num; s <= half; s++, each number can be used again in the same pass. For [1, 2, 5] that version returns true, because 4 is built as 1 + 1 + 1 + 1, which is wrong; the correct answer is false.
    • Large inputs. 200 numbers equal to 100 give a total of 20,000 and a table of 10,001 entries, and the answer true comes back at once. Changing one of the 100s to 99 makes the total odd, and the answer is false before the table is built.

    Testing

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