Start learning free

LESSON 474 OF 573 · DYNAMIC PROGRAMMING

Partition Equal Subset Sum in Scala: 0/1 Knapsack DP

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

    SCALA · DYNAMIC PROGRAMMING

    Partition Equal Subset Sum in Scala, explained

    Problem overview

    The method canPartition receives nums, an Array[Int] of positive integers, and returns a Boolean: true when the numbers can be split into two groups with equal sums, and false otherwise. Every number goes into exactly one group, and repeated values are separate numbers, each copy going 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, 11, is odd. For [1, 2, 5] it is false too: the total is 8, so each group would need 4, but no choice of the numbers makes 4.

    The lesson expects O(n * sum) time and O(sum) extra space, where n is the length of nums and sum is its total. With up to 200 numbers, trying every way to form the groups, 2^200 of them, is out of the question.

    Approach: can some numbers make half the total?

    Two equal groups can only exist when the total is even. If it is odd, the answer is false at once. Otherwise let half be the total divided by 2. If some of the numbers add up to exactly half, the remaining numbers add up to the other half. So the question becomes: can a subset of nums make the sum half?

    That is answered with dynamic programming. Keep a table of booleans, can(s), which 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, every sum that was possible before gives a new sum with num added: can(s) becomes true when can(s - num) is true. After all numbers have been handled, can(half) is the answer.

    Here is the table of reachable sums for [1, 5, 11, 5], with half = 11:

    AfterSums that can be made (up to 11)
    no numbers0
    10, 1
    50, 1, 5, 6
    110, 1, 5, 6, 11
    50, 1, 5, 6, 10, 11

    The sum 11 is reachable, so the answer is true. It was already reachable after the 11, as the 11 alone.

    Step by step

    1. Add everything up into a val total with nums.sum.
    2. Reject odd totals. If total % 2 == 1, return false. Two equal halves always add up to an even number.
    3. Compute half as total / 2.
    4. Create the table can as new Array[Boolean](half + 1). Indexes go from 0 to half, and a new Array[Boolean] starts all false.
    5. Set can(0) to true. Every sum grows from this one: a number added to no numbers makes that number's own value.
    6. Loop over the numbers with num <- nums.
    7. Loop over the sums downwards with s <- half to num by -1. A sum smaller than num can't contain it, so the range stops at num. When num is bigger than half, the range is empty and the number is skipped.
    8. Update the table: can(s) = can(s) || can(s - num). If some earlier numbers make s - num, adding num to them makes s.
    9. Return can(half) as the last expression.

    The solution in Scala

    class Solution {
    def canPartition(nums: Array[Int]): Boolean = {
        val total = nums.sum
        if (total % 2 == 1) {
            return false
        }
        val half = total / 2
        val can = new Array[Boolean](half + 1)
        can(0) = true
        for (num <- nums) {
            for (s <- half to num by -1) {
                can(s) = can(s) || can(s - num)
            }
        }
        can(half)
    }
}

    Scala details worth a look:

    • Why the sums go down. Going from half to num, the entry can(s - num) has not been changed yet for this number, so it still describes the numbers before it, and each number is used at most once. Going up would let one number feed itself: with for (s <- num to half) the answer for [1, 2, 5] becomes true, because 4 is made as 1 + 1 + 1 + 1 or 2 + 2.
    • half to num by -1 is a range that counts down and includes both ends. Without by -1, the range half to num is empty whenever num is smaller than half.
    • nums.sum adds the elements of the array. The sum is an Int, which is plenty here: at most 200 numbers of at most 100 give 20,000.
    • % and / on Int give the remainder and the quotient that truncates. The check is made for an odd total, so the division by 2 is exact afterwards.
    • The shape of the table. new Array[Boolean](half + 1) has indexes 0 to half, so can(half) is valid. The table is a one-dimensional array that is updated in place; this is why the loop direction matters.
    • || short-circuits: can(s - num) is only read when can(s) is still false.

    Complexity

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

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

    Edge cases and common mistakes

    • Odd total. [1, 2, 3, 5] returns false before the table is built.
    • A single number. [2] and [100] both return false. For [100] the total is even and half is 50, but the number is bigger than half, so its range is empty and can(50) stays false.
    • Two equal numbers. [3, 3] and [1, 1] return true.
    • Looping upwards. It reuses a number, as described above. On [1, 2, 5] it returns true, while the correct answer is false.
    • A bigger input. 200 copies of 100 return true, and 199 copies of 100 plus one 99 (an odd total) return false.

    Testing

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