AlgoVerse

Integer partitions

Count the ways to write n as a sum of positive integers (order does not matter), by dynamic programming that allows one part size at a time.

A partition of n writes it as a sum of positive integers, ignoring the order: 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 (five partitions).

Read the full explanation ↓
Input:
n=5PDF export

p(5) = 7: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1 and 1+1+1+1+1.

  1. def partitions(n):
  2. # ways[t] = the number of ways to write t as a sum of the parts allowed so far.
  3. ways = [1] + [0] * n
  4. rows = []
  5. for part in range(1, n + 1):
  6. for total in range(part, n + 1):
  7. ways[total] = ways[total] + ways[total - part]
  8. rows.append([part] + ways)
  9. return ways[n]

Invariant: After round part, ways[t] is the number of partitions of t with no part larger than part.

Start

part—
total—

The table is still empty.

Local variables

n5

Orange = changed in this step

Call stack

  1. partitions()line 1
Step 1 of 50
Black = part_done · Orange = key stepadd: 0/15 · part_done: 0/5
    Explanation

    The idea

    A partition of n writes it as a sum of positive integers, ignoring the order: 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 (five partitions).

    Dynamic programming

    Allow the parts one size at a time. When part part is added, each partition of total either does not use part (the old answer), or uses it at least once (so removing one leaves a partition of total − part):

    ways[total] ← ways[total] + ways[total − part]

    Because the inner loop goes upward, ways[total − part] already includes part; so a part can be used many times. This is the same pattern as the coin change problem.

    What to watch in the trace

    • Each table row is the whole ways array after one more part is allowed; the last filled column is the answer at that stage.