Start learning free

LESSON 477 OF 576 · DYNAMIC PROGRAMMING

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

    RUST · DYNAMIC PROGRAMMING

    Partition Equal Subset Sum in Rust, explained

    Problem overview

    The function can_partition receives nums, a vector of positive integers, and returns true when its numbers can be split into two groups with equal sums, or 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, because [1, 5, 5] and [11] both add up to 11. For [1, 2, 3, 5] the total is 11. That is odd, so no split can be equal, and the answer is false. For [1, 2, 5] the total is 8, so each group would need 4, but no group of the numbers adds up to 4, and the answer is false.

    The statement sets 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 half?

    If the total is odd, the answer is false: two equal halves always add up to an even number. Otherwise the question becomes a smaller one. Let half be the total divided by 2. If some of the numbers add up to exactly half, the rest add up to the other half. So the task is to decide whether a group of the numbers makes half.

    Trying every group is far too slow: 200 numbers can be grouped in 2^200 ways. Dynamic programming avoids that with a table of booleans: 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.

    Then add the numbers one at a time. A new number num turns every sum that could be made before into a new sum: if can[s - num] is true, then adding num makes can[s] true. After the last number, can[half] is the answer.

    Here is the table for [1, 5, 11, 5], written as the list of sums that are true:

    total = 22, half = 11, start: sums = [0]
after 1: sums = [0, 1]
after 5: sums = [0, 1, 5, 6]
after 11: sums = [0, 1, 5, 6, 11]
after 5: sums = [0, 1, 5, 6, 10, 11]
can[11] = true

    And for [1, 2, 5], where the total is 8 and half is 4:

    total = 8, half = 4, start: sums = [0]
after 1: sums = [0, 1]
after 2: sums = [0, 1, 2, 3]
after 5: sums = [0, 1, 2, 3]
can[4] = false

    The 5 changes nothing, because it is bigger than half, and 4 is never reached.

    Why the sums are visited downward

    For each number, the inner loop goes over the sums from half down to num. Going down, can[s - num] still holds the value from before this number, because the entries below s have not been updated yet. So each number is used at most once.

    Going up would break that. Then can[s - num] may already include the same number, which lets it be added again and again. On [1, 2, 5] an upward loop makes 4 as 1 + 1 + 1 + 1, and the function wrongly returns true. On [100, 1, 1], with total 102 and half 51, it also returns true, by adding the 1 fifty-one times. The correct answer for both is false.

    Step by step

    1. Add the numbers up into total, an i32, with nums.iter().sum(). The type on total tells sum() what kind of number to make.
    2. Reject an odd total. If total % 2 == 1, return false at once.
    3. Compute half as (total / 2) as usize. It is used as an index, and indexes are usize in Rust.
    4. Create the table can as vec![false; half + 1], one entry for each sum from 0 to half. Nothing above 0 can be made yet.
    5. Set can[0] to true. Every group grows from this one: one number added to no numbers makes that number's own value.
    6. Loop over &nums with the pattern &num, which borrows the vector and copies each value out of it.
    7. Loop over the sums with (num as usize..=half).rev(): from half down to num. A sum smaller than num cannot contain it. When num is bigger than half, the range is empty and the number is ignored.
    8. Update the table: can[s] = can[s] || can[s - num as usize]. A sum stays reachable if it was, and becomes reachable if s - num was.
    9. Return can[half] as the last expression.

    The solution in Rust

    impl Solution {
    fn can_partition(nums: Vec<i32>) -> bool {
        let total: i32 = nums.iter().sum();
        if total % 2 == 1 {
            return false;
        }
        let half = (total / 2) as usize;
        let mut can = vec![false; half + 1];
        can[0] = true;
        for &num in &nums {
            for s in (num as usize..=half).rev() {
                can[s] = can[s] || can[s - num as usize];
            }
        }
        can[half]
    }
}

    The Rust details worth a closer look:

    • sum() needs a type. nums.iter().sum() could produce several number types, so let total: i32 tells it which. With at most 200 numbers of at most 100, the total is at most 20000, far inside i32.
    • as usize for indexes. Vectors are indexed by usize. The values here are positive, so the casts are exact. A negative i32 would turn into a huge usize instead of failing, which is why the problem's guarantee of positive numbers matters.
    • Precedence of as. In num as usize..=half, the cast is applied to num before the range is built. In s - num as usize, it applies to num only, and then the subtraction is between two usize values.
    • (a..=b).rev(). The ..= range includes half, and rev() walks it backwards. A range whose start is above its end yields nothing, so the loop body is skipped.
    • No underflow in s - num. The loop only visits s from num upward, so the subtraction never goes below zero.
    • for &num in &nums. Iterating &nums yields &i32, and the & in the pattern copies the integer out. The vector is borrowed, not consumed.
    • Short-circuit ||. can[s - num as usize] is only read when can[s] is false. Both indexes are in range either way.
    • Final expression. can[half] has no semicolon, so it is the returned bool.

    Complexity

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

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

    Edge cases and common mistakes

    • Odd total. [1] and [1, 2, 3, 5] return false before any table is built.
    • A number bigger than half. In [100, 1, 1], the 100 can never be in a group that makes 51, so its range is empty and it changes nothing. The 1s make at most 2, so the answer is false.
    • Looping upward. It reuses a number, as shown above. This is the most common bug in this lesson.
    • Forgetting can[0] = true. Nothing would ever become true, and every answer would be false.
    • Table size. The table needs half + 1 entries, not half, so that can[half] exists.
    • Equal numbers. [1, 1] and [2, 2] return true: each copy is its own number, used once.
    • Large input. With 200 numbers of 100, the total is 20000, half is 10000, and the table has 10001 entries. It is small and fast.

    Testing

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