Start learning free

LESSON 470 OF 569 · DYNAMIC PROGRAMMING

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

Practice O(n · sum) Read the full explanation

Given a list 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

    PYTHON · DYNAMIC PROGRAMMING

    Partition Equal Subset Sum in Python, explained

    Problem overview

    The function canPartition receives a list nums 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, 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] it is False, because the total, 11, is odd and can't be split into two equal halves. For [1, 2, 5] it is also False: the total is 8, each group would need 4, and 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 once.

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

    If the total 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 others 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, every sum that could be made before gives a new sum with num added, so can[s] becomes True when can[s - num] is. Run on [1, 5, 11, 5], where half is 11, the sums that are True after each number are:

    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]

    Sum 11 appears, so the answer is True. Each row builds on the one above: the second 5 adds 5 to every sum already reachable, which brings in the new sum 10 (5 + 5).

    Why the sums go downward

    The loop over the sums runs from half down to num, not upward. Going down, can[s - num] still holds the value from before this number, because the entries below s haven't been updated yet. So num is used at most once. Going up, can[s - num] may already include num, which lets one number be used again and again. On [1, 2, 5] with half = 4, the downward loop gives these reachable sums:

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

    Sum 4 is never reached, and the answer is False. The upward loop gives:

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

    The single number 1 has already made 4, as 1 + 1 + 1 + 1, so the upward loop answers True wrongly. Problems that allow unlimited use of each value, such as counting coin combinations, go upward on purpose. This problem allows one use per number, so it goes downward.

    Step by step

    1. Add up the numbers: total = sum(nums).
    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. The total is even here, so the division is exact.
    4. Create can as [False] * (half + 1), one entry for each sum from 0 to half. No sum above 0 can be made before any number is added.
    5. Set can[0] = True. The empty group makes 0, and every other sum grows from it.
    6. Loop over nums with a variable num, adding the numbers one at a time. After the loop has handled a number, can knows every sum the numbers so far can make, each number used at most once.
    7. Loop s over range(half, num - 1, -1): every sum from half down to num. A step of -1 makes range count down, and it stops before num - 1, so num is the last sum visited. A sum below num can't contain num.
    8. Update the table: can[s] = can[s] or can[s - num]. The sum s is reachable if it already was, or if adding num to a reachable sum s - num makes it.
    9. Return can[half] after both loops.

    The solution in Python

    class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 == 1:
            return False
        half = total // 2
        can = [False] * (half + 1)
        can[0] = True
        for num in nums:
            for s in range(half, num - 1, -1):
                can[s] = can[s] or can[s - num]
        return can[half]

    The Python details worth a closer look:

    • Counting down with range. range(half, num - 1, -1) includes half and excludes num - 1. With half = 5 and num = 3 it yields 5, 4, 3. When num is bigger than half, the range is empty: list(range(4, 12, -1)) is [], so a number that is too big is ignored.
    • or returns an operand. can[s] or can[s - num] evaluates to the first operand if it is true, and to the second otherwise. With booleans the result is a boolean, so the table stays True/False.
    • // is floor division. It returns an int, which is what [False] * (half + 1) needs. A plain / gives a float such as 11.0, and multiplying a list by a float raises a TypeError.
    • Mutating while reading. The loop updates can in place and reads from the same list. That is safe only because of the downward order; a copy of the table per number would let any order work, at the cost of more memory.

    Complexity

    Time: O(n · sum). Each of the n numbers goes over at most half + 1 sums, with constant work for each. With the constraints (up to 200 numbers of up to 100), half is at most 10,000, so there are at most about two million table updates.

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

    Edge cases and common mistakes

    • An odd total. [1, 2, 3, 5] and a single number such as [1] return False without building the table.
    • A single number. [100] has an even total, but half is 50 and the 100 is skipped by the empty range, so can[50] stays False. The answer is False, as it should be: one number can't be split.
    • Two equal numbers. [2, 2] and [1, 1] return True.
    • Even total, no split. [1, 2, 5] has total 8 and returns False: an even total is necessary, not sufficient.
    • Looping upward. It lets a number be used several times, so [1, 2, 5] wrongly returns True, as the tables above show.
    • Stopping the range at num. Writing range(half, num, -1) leaves out s == num, so a number could never make its own value. [3, 3] would then fail to reach 3.
    • Forgetting can[0] = True. Every entry then stays False and the answer is always False.
    • Large inputs. 200 numbers of 100 each (total 20,000) return True in a fraction of a second.

    Testing

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