Start learning free

LESSON 475 OF 574 · DYNAMIC PROGRAMMING

Partition Equal Subset Sum in Swift: DP in O(n · sum)

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

    SWIFT · DYNAMIC PROGRAMMING

    Partition Equal Subset Sum in Swift, explained

    Problem overview

    The method canPartition receives nums, an array of positive integers, and returns true when 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: 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 it can't be split into two equal halves: false. For [1, 2, 5] the total is 8, so each group would need to add up to 4, but no group of these numbers adds up to 4: the sums up to 4 that the numbers can make are only 0, 1, 2 and 3. The answer is false.

    The statement sets a budget of 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 exactly half?

    If the total is odd, the answer is false at once, since 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 numbers that are left make the other half. So the question becomes: can some of the numbers add up to exactly half?

    Trying every possible group is too slow: 200 numbers can be grouped in 2^200 ways. Dynamic programming avoids that with 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 the numbers are added one at a time. When a number num arrives, every sum that could be made before gives a new sum with num added: can[s] becomes true when can[s - num] was already true. Here is how the table changes for [1, 5, 11, 5] (half is 11), listing the sums that are true:

    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 sum 11 is reachable, so the answer is true. For [1, 2, 5] (half is 4) the table ends as follows, and 4 is never reached:

    start  [0]
after 1   [0, 1]
after 2   [0, 1, 2, 3]
after 5   [0, 1, 2, 3]

    Why the sums go down

    The inner loop runs from half down to num. Going down, can[s - num] still holds the value from before this number was handled, because the smaller index hasn't been updated yet. So each number is used at most once. A loop that goes up would read an entry that this same number has just set, and would use the number again. On [1, 2, 5] an upward loop makes 4 as 1 + 1 + 1 + 1 or 2 + 2 and wrongly answers true. (Problems where a value may be used any number of times are the ones that go up on purpose.)

    Step by step

    1. Add everything up. let total = nums.reduce(0, +) starts from 0 and combines each number into the result with +.
    2. Reject odd totals. If total % 2 == 1, return false.
    3. Compute half as total / 2.
    4. Create can, a var array of half + 1 values false. The entry can[s] will say whether the sum s can be made.
    5. Set can[0] = true: no numbers make the sum 0, and every group grows from this entry.
    6. Loop over nums with the variable num. After the loop has handled a number, can knows every sum that the numbers so far can make, each one used at most once.
    7. Loop over the sums downward with stride(from: half, through: num, by: -1). A sum smaller than num can't contain it, so the loop stops at num.
    8. Update the table with can[s] = can[s] || can[s - num]. This is the key line: the sum s is possible if it already was, or if s - num was possible and num completes it.
    9. Return can[half] after the outer loop.

    The solution in Swift

    class Solution {
    func canPartition(_ nums: [Int]) -> Bool {
        let total = nums.reduce(0, +)
        if total % 2 == 1 {
            return false
        }
        let half = total / 2
        var can = [Bool](repeating: false, count: half + 1)
        can[0] = true
        for num in nums {
            for s in stride(from: half, through: num, by: -1) {
                can[s] = can[s] || can[s - num]
            }
        }
        return can[half]
    }
}

    The Swift details worth a closer look:

    • reduce(0, +). The operator + is itself a function, so it can be passed as the combining step. For an empty array, reduce returns the starting value 0.
    • Counting down. A closed range such as num...half can only count up. stride(from:through:by:) with by: -1 counts down, includes num, and is simply empty when num is more than half. For example stride(from: 5, through: 7, by: -1) yields nothing, while stride(from: 5, through: 2, by: -1) yields 5, 4, 3, 2.
    • A range with the bounds the wrong way crashes. A loop for s in num...half with num = 100 and half = 50 stops the program at run time, because the lower bound of a range can't be above its upper bound. This is why a big number, such as the 100 in [100], needs stride.
    • || short-circuits. can[s] || can[s - num] only looks at can[s - num] when can[s] is false. Either way the result is the same, and s - num is never negative because s starts at least at num.
    • Integer division. total / 2 truncates. That is safe here, because an odd total has already returned.

    Complexity

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

    Space: O(sum). The table holds half + 1 booleans, and nothing else grows with the input.

    Edge cases and common mistakes

    • Odd total. [1, 2, 3, 5] returns false before the table is even built.
    • A number bigger than half. For [100] the total is 100, half is 50, and the number 100 is more than 50. The stride is empty, can[50] stays false, and the answer is false.
    • Two equal numbers. [1, 1] returns true: each copy is its own number, and goes to its own group.
    • An even total that can't be split. [2, 2, 2, 2, 2] has a total of 10 and a half of 5, but sums of 2s are always even, so it returns false. Checking the parity of the total is necessary but not enough.
    • Going up instead of down. Written with the sums counted upward and a guard for numbers above half, the loop answers true for [1, 2, 5], which has no valid split.
    • Initial value. Without can[0] = true nothing is ever reachable, and every answer is 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, 2, 2, 2] gives false.
    • [3, 3, 3, 4, 5] gives true: 4 + 5 and 3 + 3 + 3 both make 9.
    Keep going with Swift500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free