Start learning free

LESSON 470 OF 569 · DYNAMIC PROGRAMMING

Partition Equal Subset Sum in Java: 1D 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

    JAVA · DYNAMIC PROGRAMMING

    Partition Equal Subset Sum in Java, explained

    Problem overview

    The method canPartition receives an int[] named nums of positive integers and returns true when its 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, since the total, 11, is odd. For [1, 2, 5] it is also false: the total is 8, each group would need 4, but the numbers can only make 1, 2, 3, 5, 6, 7 and 8.

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

    If the total is odd, two equal halves are impossible. 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 selection of numbers, each used at most once, add up to half?

    Trying every selection is hopeless: 200 numbers can be grouped in 2^200 ways. Dynamic programming keeps a table of booleans instead. can[s] says whether some of the numbers seen so far can 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.

    The numbers are added 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. Here is how can grows for [1, 5, 11, 5], with half = 11, listing the sums that are true:

    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 last number, 11 is in the list, so the answer is true.

    Why the inner loop goes down

    The loop over sums runs from half down to num. Going down, 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 a number build on its own earlier update and be used again and again. That is the right behavior for a problem where a coin can be used many times, but wrong here. The run shows it: with an upward loop, [1, 2, 5] gives true, as if 4 were 1 + 1 + 1 + 1 or 2 + 2, while the downward loop gives false.

    Step by step

    1. Sum the numbers into total with Arrays.stream(nums).sum(). The stream turns the array into a sequence of its numbers, and sum() adds them.
    2. Return false if total % 2 == 1. Two equal halves always give an even total.
    3. Store total / 2 in half. This is the target for one group.
    4. Create can, a boolean[] of size half + 1. New boolean arrays start all false.
    5. Set can[0] = true. The empty selection makes 0, and every other sum grows from it.
    6. Loop over the numbers with an enhanced for. After a number is handled, can knows every sum the numbers so far can make.
    7. Loop over the sums from half down to num. A sum smaller than num cannot contain it.
    8. Update with can[s] = can[s] || can[s - num]. If some earlier numbers make s - num, adding num makes s.
    9. Return can[half].

    The solution in Java

    class Solution {
    public boolean canPartition(int[] nums) {
        int total = Arrays.stream(nums).sum();
        if (total % 2 == 1) {
            return false;
        }
        int half = total / 2;
        boolean[] can = new boolean[half + 1];
        can[0] = true;
        for (int num : nums) {
            for (int s = half; s >= num; s--) {
                can[s] = can[s] || can[s - num];
            }
        }
        return can[half];
    }
}

    Java details: boolean[] is initialized to false, which is what the table needs. Arrays.stream(nums) on an int[] gives an IntStream, whose sum() returns an int. With at most 200 numbers of at most 100 the total stays far below the int limit, so overflow is not a concern. In can[s] || can[s - num], the || short-circuits, but both operands are plain array reads, so the order has no side effects. The inner loop's condition s >= num also guarantees that s - num is never negative.

    Complexity

    Each of the n numbers goes over at most half + 1 sums, with constant work for each, so the time is O(n · sum), where sum is the total. The table holds half + 1 booleans, so the extra space is O(sum). For 200 numbers equal to 100, the total is 20000 and the method still answers true quickly.

    Edge cases and common mistakes

    • Odd total. [2] and [1, 2, 3, 5] return false immediately.
    • A number larger than half. The inner loop does not run for it, because half >= num is false, and the answer comes from the other numbers. For [100, 100, 100, 100, 99] the total is odd, so the answer is false.
    • Looping up instead of down. Numbers get reused, and [1, 2, 5] wrongly gives true.
    • Forgetting can[0] = true. Then nothing can ever become true, and every answer is false.
    • Checking only for an even total. An even total is necessary, not sufficient, as [1, 2, 5] shows.
    • Table of size half. Index half would be out of range; the table needs half + 1 entries.

    Testing

    These inputs were run against the solution above:

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