Start learning free

LESSON 473 OF 572 · DYNAMIC PROGRAMMING

Partition Equal Subset Sum in C#: Dynamic Programming, 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

    C# · DYNAMIC PROGRAMMING

    Partition Equal Subset Sum in C#, explained

    Problem overview

    The method CanPartition receives an int[] named nums of positive integers and returns a bool: can the numbers be split into two groups with equal sums? Every number goes into exactly one group, and repeated values are separate numbers.

    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 cut into two equal halves. For [1, 2, 5] it is also false: the total 8 asks for two groups of 4, and the numbers can only make 1, 2, 3, 5, 6, 7 and 8, never 4.

    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 half, the rest add up to half too, so the question becomes: can a selection of the numbers make exactly half?

    Trying every selection is hopeless: 200 numbers can be grouped in 2^200 ways. Instead keep a table of booleans, can[s], which 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. For a number num, every sum that could be made before gives a new sum with num added: can[s] becomes true if can[s - num] was true. This is dynamic programming: each entry reuses answers for smaller sums. Here is the table for [1, 5, 11, 5], with the sums that are true after each number:

    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 half is 11, and 11 is true after the third number, so the answer is true.

    Why the sums go down

    The inner loop goes from half down to num. Going down, can[s - num] still holds its value from before this number, because smaller indexes are updated later. So each number is used at most once. Going up would let the same number feed itself: after can[1] becomes true, can[2] would use it, and then can[3], and so on, so a number could be used many times. For [1, 2, 5] the upward version returns true, using 1 + 1 + 1 + 1 or 2 + 2 to make 4, while the correct answer is false. The table with the downward loop shows the right behaviour:

    start      0
after   1  0 1
after   2  0 1 2 3
after   5  0 1 2 3

    Half of 8 is 4, and 4 never appears.

    Step by step

    1. Add up the numbers into an int named total with nums.Sum().
    2. Reject odd totals. If total % 2 == 1, return false.
    3. Compute half = total / 2.
    4. Create can, a bool[] of length half + 1. A new bool array is all false.
    5. Set can[0] = true: no numbers make the sum 0, and every other sum grows from it.
    6. Loop over the numbers with foreach.
    7. Loop over the sums downward: s from half while s >= num, because a sum smaller than num can't contain it.
    8. Update: can[s] = can[s] || can[s - num]. A sum stays reachable if it already was, and becomes reachable if s - num was.
    9. Return can[half].

    The solution in C#

    class Solution {
    public bool CanPartition(int[] nums) {
        int total = nums.Sum();
        if (total % 2 == 1) {
            return false;
        }
        int half = total / 2;
        bool[] can = new bool[half + 1];
        can[0] = true;
        foreach (int num in nums) {
            for (int s = half; s >= num; s--) {
                can[s] = can[s] || can[s - num];
            }
        }
        return can[half];
    }
}

    The C# details worth knowing:

    • nums.Sum() is a LINQ extension method from System.Linq. In a file of your own, add using System.Linq; at the top. The method adds the elements as int.
    • The remainder operator. total % 2 == 1 is a correct test for an odd total here because the numbers are positive, so the total is positive. For negative values % can give -1, so total % 2 != 0 is the safer habit.
    • Integer division. total / 2 truncates, and the odd case was already rejected, so it is exact.
    • Short-circuit ||. In can[s] || can[s - num], the right side is only read when the left side is false. Both indexes are always inside the array: s <= half and s - num >= 0 by the loop condition.

    Complexity

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

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

    Edge cases and common mistakes

    • Odd total. [3] and [1, 2, 3, 5] return false before the table is built.
    • One number. [2] has an even total, but half is 1 and 1 can't be made, so the answer is false.
    • Two equal numbers. [1, 1] returns true.
    • A number bigger than half. In [1, 2, 9] the total is 12 and half is 6. The inner loop never runs for 9, so it is never used, and the answer is false.
    • Looping upward. It reuses numbers and gives true for [1, 2, 5].
    • Looping down to 0. The condition s >= num matters; with s >= 0 instead, can[s - num] reads a negative index when s < num and can[s] is still false, and that throws an IndexOutOfRangeException. (When can[s] is already true, || skips the read, so some inputs, such as {1, 1}, still run.)
    • Forgetting can[0] = true. Every entry stays false, and the method always returns false.

    Testing

    • [1, 5, 11, 5] gives true.
    • [1, 2, 3, 5] gives false.
    • [1, 2, 5] gives false.
    • [1, 1] gives true.
    • [2] and [3] give false.
    • [1, 2, 9] gives false.
    • [1, 2, 3, 4, 5, 6, 7] gives true.
    • Two hundred copies of 100 give true.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free