Partition into equal subsets with Python int bit rows

Why this matters

Suppose three friends share a bill with ten items of different prices. They want to split the items into two piles that cost the same. Can it be done? Programmers call this the partition problem. The same question appears when two servers should get about the same amount of work, or when a list of jobs must be cut into two halves of equal total size.

Trying every way to split the items is slow. This lesson uses dynamic programming (DP). DP means solving a small question, writing the answer in a table, and reusing the table for the bigger questions. The table here holds yes and no answers. The second half of the lesson stores the same table as one Python int, a whole number that holds as many bits as it needs. A single operation then updates many answers at once. That is the bitset trick.

This lesson only asks the yes or no question. The next lesson in this module, Target sum by transforming to subset sum, uses a similar table to count the answers instead.

Words you need first

A subset is a group made by picking some of the items and leaving the rest. From the list [1, 5, 11, 5] you can pick [5, 11], or [1, 5], or nothing at all. The empty subset is allowed.

A sum is the total of the numbers in a group. The sum of [5, 11] is 16. Python's built-in sum() adds up a list for you: sum([5, 11]) gives 16.

A table here is a list with one cell for each possible sum. Cell number s holds True when some subset adds up to exactly s, and False when none does. Python counts list positions from 0, so the first cell is number 0.

A bit is a single digit, 0 or 1. A row of True and False values can be written as a row of 0 and 1 digits. A Python int holds a whole number with as many bits as it needs. The operators << (shift left), >> (shift right), | (OR) and & (AND) work on all of those bits in one step.

Shift left by x moves every bit x places to the left. In binary, shifting left by one place doubles a number. The binary number 101 is 5, and shifted left by one it becomes 1010, which is 10. In Python, 5 << 1 gives 10. In a row of sum flags, shifting left by x means that every reachable sum s becomes a reachable sum s + x.

OR combines two rows bit by bit. A position is 1 in the result when it is 1 in either row.

A mask is a number with only some bits set to 1. Combining a number with a mask using AND keeps the bits where the mask is 1 and clears the others.

The question

Take the list [1, 5, 11, 5]. Its total is 1 + 5 + 11 + 5 = 22. If the two groups have equal sums, each group must add up to 11. Half the total is the target.

Two rules follow from this.

• If the total is odd, no equal split is possible. Half of an odd number is not a whole number, so two equal whole-number sums cannot add up to it. The list [1, 2, 3, 5] has a total of 11, so the answer is no.
• If the total is even, the question becomes: can some subset of the numbers add up to exactly half the total? For [1, 5, 11, 5] the answer is yes. The single number 11 is one group with sum 11, and the other group is 1 + 5 + 5, which also adds to 11.

Once one group reaches the target, the other group must reach it too, because the two groups together add up to the total. So one subset question is enough.

The simplest method checks every subset. A list of n numbers has 2 to the power n subsets. For 4 numbers that is 16 subsets, which is quick to check by hand. For 40 numbers it is 2 to the power 40, which is 1,099,511,627,776 subsets. The table method below does much less work.

Step 1: a table of yes and no cells

Build a list called can_make with one cell for each sum from 0 up to the target. Set can_make[0] to True, because the empty subset adds up to 0. Every other cell starts as False. In Python, [False] * (target + 1) builds that list in one line.

Now take the numbers one at a time. Suppose a sum s - x is already reachable. Then adding the number x makes sum s reachable. So for each number x, go through the cells and set can_make[s] to True when can_make[s - x] is True.

Here is a complete program for the list [1, 5, 11, 5]. It prints the table after each number.

The output is:

numbers: [1, 5, 11, 5]
total: 22
target: 11
start:      100000000000
after  1:   110000000000
after  5:   110001100000
after 11:   110001100001
after  5:   110001100011
can split equally: True

Read each row as a set of flags. The digit at position s is 1 when sum s can be reached. The first row has only position 0 set, because only the empty subset exists at the start. After the number 1, positions 0 and 1 are set. After the number 5, the sums 5 and 6 are added, because 0 + 5 and 1 + 5 are reachable. After the number 11, position 11 turns on. That is the target, so the last line says True.

The line can_make[s] = can_make[s] or can_make[s - x] reads as "this cell is already true, or the cell x steps back is true". Both sides are True or False, so or gives a True or False result.

Why the inner loop runs backwards

The inner loop is for s in range(target, x - 1, -1). It starts at the target and goes down to x. The end value x - 1 is not included in a range, so the last value the loop uses is x. That keeps s - x from going below 0.

The reason for going down is that the cell s - x must still hold the value from before this number was processed. When s goes down, the cell s - x is smaller than s, so it has not been changed yet in this pass. Each number is therefore used at most once.

If the loop went upwards, a cell could be changed early in the pass and then read again later in the same pass. That lets one number be used twice. The mistakes section shows this with a real output.

Step 2: the same table as one int

A row of true and false values holds the same information as a row of bits. Read the row as a binary number where bit s is the answer for sum s. In Python, the answer for sum s is (reach >> s) & 1. The shift moves bit s to position 0, and the AND keeps only that bit.

At the start only sum 0 is reachable, so the row has bit 0 set and no other bits. In Python that row is the int 1.

Adding a number x means that every reachable sum s gives a new reachable sum s + x. In bit terms, take the whole row, shift it left by x places, and combine it with the old row using OR. The old row keeps every sum that was already reachable, which covers the case where x is left out. The shifted row adds every sum that becomes reachable when x is put in.

A small example with the list [2, 3, 5] and target 5 shows the idea. Each line is one row written as binary, with the sums that are set listed in the right-hand column.

start            1        sums 0
shift 2 gives 100         sum 2
OR, after 2      101      sums 0, 2
shift 3 gives 101000      sums 3, 5
OR, after 3      101101   sums 0, 2, 3, 5

The last line has bit 5 set, so the target 5 is reachable.

Here is the bitset version of the same program.

Its output is:

numbers: [1, 5, 11, 5]
start:      100000000000
after  1:   110000000000
after  5:   110001100000
after 11:   110001100001
after  5:   110001100011
can split equally: True

The rows match the list version exactly. That match is a useful check when you write this kind of code yourself.

Why the bitset version needs no backwards loop

The list version needed the backwards loop so that a number was not used twice. The bitset version gets the same guarantee from the order of its steps. reach << x reads the old value of reach, and the result is only stored after the OR finishes. The whole row is updated in one step, so no cell is read after it has changed.

The mask

Every shift moves bits to the left, so the number grows each time. Python ints have no size limit, so nothing stops the growth. Sums above the target are never needed, so the program throws them away. The mask has bits 0 to target set. The & mask part keeps only those bits.

The mask is built as (1 << (target + 1)) - 1. The expression 1 << (target + 1) is a 1 followed by target + 1 zeros. Subtracting 1 turns that into target + 1 ones, which fill positions 0 to target.

Why one step covers many sums

CPython, the standard Python program, stores an int in pieces of 30 bits called digits. On this build sys.int_info.bits_per_digit is 30. The shift and OR code runs in C and works on whole digits, so one operation covers about 30 sums at a time. A list needs one Python-level assignment for each cell. This is where the speed of the trick comes from.

Step 3: a harder example

Here is a list where the total is even but the answer is still no. The program below is the bitset version run on four lists. It prints the final row and the answer for each one.

Its output is:

numbers: [1, 5, 11, 5]
total: 22
target: 11
final row: 110001100011
answer: True
 
numbers: [1, 2, 3, 5]
total: 11
odd total, answer: False
 
numbers: [3, 34, 4, 12, 5, 2]
total: 60
target: 30
final row: 1011111111111011111111111010000
answer: False
 
numbers: [2, 2, 3, 5, 7, 9]
total: 28
target: 14
final row: 101111011111111
answer: True

The list [3, 34, 4, 12, 5, 2] has an even total of 60, so the odd check does not stop it. Its target is 30. The row has a 0 at position 30, so no subset adds up to 30. An even total is necessary, but it does not guarantee an answer.

The list [2, 2, 3, 5, 7, 9] has target 14, and position 14 is 1. The subset 2 + 5 + 7 adds to 14. The other group is 2 + 3 + 9, which also adds to 14.

Step 4: memory and speed

Memory

A list stores one reference for each cell. A reference is a pointer to the object True or False. On a 64-bit build each one takes 8 bytes. A bytearray stores one byte for each cell, which is the same idea as Java's boolean[]. The bit row stores one bit for each cell. The program below measures all three for a target of 50,175, so the row has 50,176 cells.

Its output is:

list of bools, bytes: 401464
bytearray, bytes: 50233
int used as bit row, bytes: 6716
bits per digit inside an int: 30

The numbers depend on the Python build and the machine, so yours may differ a little. The pattern does not change: the list is about 60 times larger than the bit row. The bit row is one int object, so its size is its 30-bit digits plus a small header.

Speed

The next program compares the two methods on a list of 200 random numbers between 1 and 1000. The random seed is fixed, so the list is the same on every run. The program tries each method three times and keeps the fastest time. It also checks both methods against a brute force search on 2000 small random lists.

Its output is:

checked 2000 random lists, 519 could be split
n = 200, total = 93300
list answer:   True
bitset answer: True
answers agree: True
list, best run: 169.69 ms
bitset, best run: 0.25 ms

The times come from one machine and one run. Your numbers will differ, but the pattern is what matters. The bit version did the same work in far fewer steps here. Each list cell costs one Python-level assignment, while the shift and OR run as one C operation.

The limit

The row length is total // 2 + 1. The cost depends on the total, not on how many numbers there are. A list whose total is 1,000,000,000 needs a row of 500,000,001 bits, which is about 62.5 MB. Every number then shifts and copies a row that size, so the run takes far longer than the test above. This method suits totals in the thousands to a few million. Larger totals need a different method.

Common mistakes

Forgetting the odd total check

In Python, total // 2 drops the remainder just as Java's integer division does. The target is then a number that cannot be split exactly, but the table can still say yes. This program skips the check:

Its output is:

total 11, target from // 5
without the odd check, can_make[target] = True

The answer is wrong. The number 5 alone is a subset that adds to 5, so the table says yes. But the two groups would need to add to 5.5 each, which is impossible. The odd check on total % 2 must come first.

Using / instead of //

In Python 3, / always gives a float, a number with a decimal part. 11 / 2 is 5.5, not 5. A list cannot be built with a float size, so Python raises an error. The program catches it and prints the message:

Its output is:

11 / 2 is 5.5
TypeError: can't multiply sequence by non-int of type 'float'

Use // whenever the result is used as a size, an index or a target.

Looping forwards

This program runs the inner loop from low to high. It is the same code as before, with the loop direction changed:

Its output is:

forwards row: 111
can make 2 from [1]? True

The list has one 1, but the answer says that 2 can be made. The forward loop sets cell 1 from cell 0, and then cell 2 from the new cell 1. The number 1 is used twice. Going backwards fixes it, because cell 1 is still False when cell 2 is read.

Forgetting the lower bound

If the loop is written as range(target, -1, -1), then the index s - x goes below 0 when s < x. Java stops the program with an error here. Python does not. A negative index counts from the end of the list, so can_make[-1] is the last cell. The program keeps running with a wrong value.

This program shows the difference. It runs the correct loop and the loop without the bound side by side:

Its output is:

after 4 correct: 100010 buggy: 101010
after 6 correct: 100010 buggy: 101010
sum 2 reachable? False buggy says True

The buggy row has a 1 at position 2, but no subset of [4, 6] adds to 2. The bug is silent, so the wrong row is only found by comparing against a correct one or against a brute force check. Python raises IndexError only when the index is less than minus the length of the list. The fix is the range(target, x - 1, -1) form used in every program in this lesson.

Integers do not overflow

Python int has no fixed size. The number keeps growing until the computer runs out of memory. The next two lines show a sum that would be too big for a 32-bit Java int, and a power that is far bigger than a 64-bit number:

Its output is:

3000000000
1267650600228229401496703205376

So the risk of wrap-around does not apply here. The cost moves elsewhere: a large total makes the bit row large and slow, as the limit section explains.

A mask one bit too short

The mask must keep bit target. A mask made with (1 << target) - 1 instead of (1 << (target + 1)) - 1 has bits 0 to target - 1 only, and it deletes the one bit that the answer needs. The program below uses the list [3, 3] with target 3:

Its output is:

short mask, sum 3 reachable: False
correct mask, sum 3 reachable: True

Use target + 1 as shown in Step 2.

Asking for a negative bit

Python's >> operator refuses a negative shift. A negative position usually means the target itself is negative, which happens when the list has a negative number in it or when the total was computed wrong. The lists in this lesson are all positive, so the check does not come up here. This program shows the message:

Its output is:

ValueError: negative shift count

Practice

Exercise 1. Can the list [4, 4, 4, 4] be split into two equal groups?

Show the answer

The total is 16, so the target is 8. Two of the 4s add to 8, and the other two add to 8, so the answer is yes.

Exercise 2. Can the list [1, 2, 4, 8] be split into two equal groups?

Show the answer

The total is 15, which is odd. No equal split is possible, so the answer is no. The table method is not needed for this one.

Exercise 3. Write the table row after each number for the list [2, 3, 5] with target 5, using the yes and no table from Step 1. Give the answer.

Show the answer

Start with the row 100000 (cells 0 to 5). After 2, cells 0 and 2 are true: 101000. After 3, cells 0, 2, 3 and 5 are true: 101101. After 5, cell 5 is already true, so the row stays 101101. Cell 5 is true, so the answer is yes.

Exercise 4. The bitset program in Step 2 ends with a row of bits. Change it so that it prints how many sums from 0 to the target can be reached. Do not use a loop.

Show the answer

Add the line print("reachable sums:", reach.bit_count()) in place of the last print. int.bit_count() counts the 1 bits in an int. The mask keeps only bits 0 to the target, so the count covers exactly the reachable sums in that range. For the list [2, 3, 5], the row 101101 has four set bits, which means four reachable sums: 0, 2, 3 and 5.

Exercise 5. Explain in your own words why the bitset version does not need a backwards loop.

Show the answer

The shifted copy is made from the old value of reach, and the new value is stored only after the OR finishes. The whole row is replaced in one step, so no cell is read after it has been changed. A number cannot be used twice.

Summary

• A list can be split into two equal groups only when its total is even and some subset adds up to half the total.
• The list method stores one yes or no cell for each sum from 0 to the target. It loops backwards with range(target, x - 1, -1) so that each number is used once.
• The bitset method stores the same table as one Python int. Each number is handled by one shift and one OR, followed by a mask that keeps bits 0 to the target.
• A Python list of bools uses about 60 times the memory of the bit row for the same table, and each shift or OR handles many sums at once.
• The cost depends on half the total, so this method fits totals in the thousands to a few million. Python ints do not overflow, but a large total still makes the row large and slow.