Start learning free

LESSON 474 OF 573 · DYNAMIC PROGRAMMING

Partition Equal Subset Sum in Kotlin: 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

    KOTLIN · DYNAMIC PROGRAMMING

    Partition Equal Subset Sum in Kotlin, explained

    Problem overview

    The method canPartition receives nums, an IntArray of positive integers, with up to 200 values from 1 to 100. It returns 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] the total is 11, which is odd, so two equal halves are impossible. For [1, 2, 5] the total is 8, so each group would need to add up to 4, and no choice of those three numbers makes 4, so the answer is false.

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

    Approach: can some of the numbers make half?

    If the total is odd, the answer is false at once. If it is even, call half of it half. When some of the numbers add up to exactly half, the numbers left over add up to the other half. So the question becomes: can some subset of nums sum to half?

    Trying every subset is hopeless: 200 numbers can be grouped in 2^200 ways. Dynamic programming avoids that by remembering which sums are reachable. Keep a table 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, because no numbers at all make 0.

    Now add the numbers one at a time. For a number num, every sum that was reachable before gives a new reachable sum with num added. So can[s] becomes true when can[s - num] was true. Taking the sums from half down to num is the detail that matters: going down, can[s - num] still has its value from before this number, so the number is used at most once. Going up, can[s - num] could already include the same num, which would use it again.

    The same table with the loop going up is the pattern for problems where an item can be used any number of times. Here each number is used once, so the loop runs down.

    Step by step

    1. Add the numbers up with nums.sum() and store the result in total.
    2. Reject an odd total. If total % 2 == 1, return false: two equal halves always add up to an even number.
    3. Store half as total / 2. The goal is now to make exactly half from some of the numbers.
    4. Create can, a BooleanArray of half + 1 entries. A new boolean array starts all false.
    5. Set can[0] = true. The empty selection makes 0, and every other sum grows from it.
    6. Loop over nums with the variable num. After each pass, can describes all sums that the numbers handled so far can make.
    7. Loop s over half downTo num. A sum smaller than num can't contain it, so the loop stops at num.
    8. Update the table: can[s] = can[s] || can[s - num]. Either s was reachable already, or s - num was and adding num reaches it.
    9. Return can[half] after the outer loop.

    The solution in Kotlin

    class Solution {
    fun canPartition(nums: IntArray): Boolean {
        val total = nums.sum()
        if (total % 2 == 1) {
            return false
        }
        val half = total / 2
        val can = BooleanArray(half + 1)
        can[0] = true
        for (num in nums) {
            for (s in half downTo num) {
                can[s] = can[s] || can[s - num]
            }
        }
        return can[half]
    }
}

    Kotlin details worth knowing:

    • nums.sum() on an IntArray returns an Int. With at most 200 values of at most 100 each, the total is at most 20,000, far from the 32-bit limit, so there is no overflow to worry about.
    • downTo is a range that counts down. half downTo num includes both ends. When num is bigger than half, the range is empty and the loop body never runs.
    • val can and mutable entries. val means the name always refers to the same array, but its elements can still change.
    • || short-circuits: when can[s] is already true, the right side is not evaluated. It makes no difference to the result here.
    • The remainder operator. total % 2 == 1 works for the positive totals of this lesson. The check is safe because every number is positive.

    Tracing the example

    For [1, 5, 11, 5], the total is 22 and half is 11. Printing the sums marked true in can 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]

    After the 11, the sum 11 is reachable (11 alone), so can[11] is true and the method returns true. The second 5 adds 10 as well, from 5 + 5.

    Complexity

    Time: O(n · sum). Each of the n numbers goes over at most half + 1 sums with constant work for each. The sum is at most 20,000 here, so the largest input needs about two million steps.

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

    Edge cases and common mistakes

    • Odd total. [1, 2, 3, 5] and [1, 1, 3] return false without touching the table.
    • A single number. [1] returns false: its total is odd. Even a single number can never be split, since the other group would be empty with sum 0, and every number is at least 1.
    • A number bigger than half. In [100, 1, 1], the total is 102 and half is 51. The 100 doesn't fit in the table, its loop does nothing, and the answer is false.
    • Equal numbers. [2, 2] and [100, 100] return true: the copies are separate numbers, and each goes into one group. Twelve 1s also return true.
    • Looping upward. If the inner loop runs num..half, a number can be counted several times. With that change, [1, 2, 5] returns true, because 4 can be made as 1 + 1 + 1 + 1 or 2 + 2, and [100, 1, 1] returns true too, with fifty-one 1s. The downward loop returns false for both.
    • Largest input. Two hundred 100s give true. Changing one of them to 99 makes the total 19,999, which is odd, so the answer is false.

    Testing

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