Integer Partition Algorithms: Complete Mathematical Guide

Introduction and Core Concepts

An integer partition of a positive integer n is a way of writing n as a sum of positive integers where the order of summands does not matter. For example, the integer 4 has five partitions: 4, 3+1, 2+2, 2+1+1, and 1+1+1+1. By convention, partitions are typically written in non-increasing order to avoid counting permutations as distinct. The study of integer partition algorithms encompasses the methods for generating, counting, enumerating, and analyzing these decompositions efficiently.

Integer partitions are fundamental objects in additive number theory and combinatorics. The partition function p(n) denotes the number of distinct partitions of n. This function grows extremely rapidly: p(10) = 42, p(50) = 204226, p(100) = 190,569,292, and p(200) is approximately 3.97 x 10^12. This explosive growth is formalized by the Hardy-Ramanujan asymptotic formula, which states that p(n) ~ (1 / (4n * sqrt(3))) * exp(pi * sqrt(2n/3)). Understanding this growth is critical for algorithm design because any algorithm that explicitly enumerates all partitions must be exponential.

Integer partition algorithms matter far beyond pure mathematics. They form the backbone of dynamic programming education, serve as a canonical example of recursion with memoization, and illustrate the power of generating functions. In computer science, they appear in resource allocation problems, load balancing, parallel task scheduling, and combinatorial optimization where a total resource must be divided into unordered chunks. Mastery of partition algorithms provides deep insight into recurrence relations, state compression, and the trade-off between counting and enumeration.

Fundamental Definitions

A partition of n is a multiset of positive integers whose sum is n. Each element in the multiset is called a part. The number of parts is the length of the partition, and the largest part is often used as a constraint in restricted partition problems. A partition can be represented visually using a Ferrers diagram or Young diagram, where rows of dots or boxes correspond to parts in non-increasing order.

Restricted partitions add constraints that make the problem more tractable and more applicable. Common restrictions include partitions into distinct parts, partitions into odd parts, partitions with bounded largest part, partitions with bounded number of parts, and partitions into a specific set of allowed summands. Euler's famous theorem states that the number of partitions of n into distinct parts equals the number of partitions of n into odd parts, a result with profound algorithmic implications for bijection-based generation.

• p(n): The unrestricted partition function counting all partitions of n.
• p_k(n): Number of partitions of n into exactly k parts.
• q(n): Number of partitions of n into distinct parts.
• p(n, k): Number of partitions of n with largest part at most k.
• Conjugate Partition: The partition obtained by transposing the Ferrers diagram, swapping rows and columns.

How It Works

At its core, integer partition theory relies on recursive decomposition. Any partition of n either contains a part of size k or it does not. This simple observation leads to the fundamental recurrence: p(n, k) = p(n, k-1) + p(n-k, k), where p(n, k) is the number of partitions of n with largest part at most k. The first term counts partitions that do not use k, while the second counts those that use at least one k. The base cases are p(0, k) = 1, p(n, 0) = 0 for n > 0, and p(n, k) = p(n, n) for k > n. This recurrence is the foundation for most dynamic programming counting algorithms.

Generating functions provide the second major theoretical pillar. The ordinary generating function for p(n) is given by the infinite product: sum_{n>=0} p(n) * x^n = product_{i>=1} 1 / (1 - x^i). Each factor 1 / (1 - x^i) = 1 + x^i + x^{2i} + ... represents the choice of how many copies of part i to include. Euler's pentagonal number theorem gives a powerful recurrence for p(n) itself without the auxiliary parameter k: p(n) = sum_{k != 0} (-1)^{k+1} p(n - k(3k-1)/2), where k runs over 1, -1, 2, -2, ... and p(0)=1, p(n)=0 for n < 0. This reduces counting p(n) to O(n * sqrt(n)) time.

For explicit enumeration, algorithms use lexicographic or reverse-lexicographic generation rules that produce each successive partition from the previous one in O(1) amortized time. The classic RuleAsc algorithm by McKay and Knuth generates partitions in ascending order (non-decreasing parts), while RuleDesc generates them in descending order. These algorithms maintain an array representing the current partition and a pointer to the active part, using transformations that redistribute the remainder after decrementing a part. They avoid recursion overhead and are optimal for exhaustive generation.

The Recurrence Tree and State Space

Conceptually, you can view the search space as a tree where each node represents a decision about the next part. Starting with remainder n and maximum allowed part n, you branch on choosing a part i from 1 to max_allowed. Recursively, you partition n-i with max_allowed = i to enforce non-increasing order and avoid duplicates. Pruning occurs when remainder reaches zero (a complete partition) or when no valid parts remain. Memoization collapses this exponential tree into a DAG for counting problems, since many subproblems p(rem, max) are repeated.

Ferrers Diagrams and Conjugacy

The Ferrers diagram provides a geometric interpretation that is crucial for optimization. The conjugate of a partition is obtained by reading column heights instead of row lengths. This bijection proves that the number of partitions of n with largest part at most k equals the number of partitions of n with at most k parts. Algorithmically, this duality allows you to choose the smaller dimension for DP tables, significantly reducing space when k is large or small relative to n.

Implementation

Implementing integer partition algorithms requires careful handling of recursion depth, duplicate avoidance, and integer overflow, as p(n) grows extremely fast. Below are four canonical implementations covering enumeration, counting via DP, counting via Euler's recurrence, and iterative generation. All code is written for clarity and includes detailed comments on state invariants.

1. Recursive Enumeration (Generates All Partitions)

This approach is the most intuitive and directly mirrors the recurrence p(n, k). It builds partitions in non-increasing order by passing the maximum allowed next part. While simple, it creates many intermediate lists and is best for n <= 30 where enumeration is feasible.

def partitions_recursive(n: int, max_part=None) -> list:
    """
    Generate all integer partitions of n in non-increasing order.
    Uses recursion with max_part to enforce ordering and avoid duplicates.
    """
    if max_part is None:
        max_part = n  # Initially any part up to n is allowed
    
    # Base case: exact sum reached, one valid partition (empty suffix)
    if n == 0:
        return [[]]
    
    # No valid partition if remainder negative or no parts allowed
    if n < 0 or max_part == 0:
        return []

    result = []
    # Try every possible next part i from min(max_part, n) down to 1
    # Descending order guarantees non-increasing sequence
    for i in range(min(max_part, n), 0, -1):
        # Recursively partition the remainder n-i with new limit i
        for suffix in partitions_recursive(n - i, i):
            result.append([i] + suffix)
    return result

# Example: partitions_recursive(5) returns 7 partitions
# [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]

2. Dynamic Programming Counting (O(n*k) Table)

When you only need the count p(n, k) rather than the partitions themselves, a DP table is far more efficient. This bottom-up method fills a 2D table dp[i][j] = number of partitions of i with largest part <= j. It avoids recursion and repeated work.

def count_partitions_dp(n: int, k: int = None) -> int:
    """
    Count partitions of n using bottom-up DP.
    dp[i][j] = partitions of i with max part <= j
    Recurrence: dp[i][j] = dp[i][j-1] + dp[i-j][j] if i >= j
    """
    if k is None:
        k = n
    if n < 0:
        return 0
    
    # dp[i][j] for 0 <= i <= n, 0 <= j <= k
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    
    # Base case: one way to partition 0 (empty partition)
    for j in range(k + 1):
        dp[0][j] = 1
    
    for i in range(1, n + 1):
        for j in range(1, k + 1):
            # Case 1: do not use part j
            dp[i][j] = dp[i][j - 1]
            # Case 2: use at least one j, if possible
            if i >= j:
                dp[i][j] += dp[i - j][j]
    return dp[n][k]

# count_partitions_dp(100) = 190569292
# count_partitions_dp(100, 5) = partitions with parts <= 5

3. Euler's Pentagonal Number Theorem (O(n*sqrt(n)))

For computing p(n) alone without a bound k, Euler's recurrence is asymptotically faster than the O(n^2) DP table. It uses generalized pentagonal numbers g(k) = k*(3*k - 1)//2 for k = 1, -1, 2, -2, ...

def count_partitions_euler(n: int) -> int:
    """
    Count p(n) using Euler's pentagonal number theorem.
    p(n) = sum_{k != 0} (-1)^(k+1) * p(n - g(k))
    where g(k) = k*(3*k - 1)//2, k = 1, -1, 2, -2, ...
    Time: O(n * sqrt(n)), Space: O(n)
    """
    if n < 0:
        return 0
    if n == 0:
        return 1
    
    # p[i] will store p(i) for i = 0..n
    p = [0] * (n + 1)
    p[0] = 1
    
    for i in range(1, n + 1):
        total = 0
        k = 1
        while True:
            # Generate pentagonal numbers for k and -k
            g1 = k * (3 * k - 1) // 2
            if g1 > i:
                break
            
            # Sign is (-1)^(k+1): +, +, -, -, +, +, ...
            # For k=1: +, k=2: -, k=3: +, etc. Adjusted for both g1 and g2
            sign = 1 if k % 2 == 1 else -1
            
            total += sign * p[i - g1]
            
            g2 = k * (3 * k + 1) // 2  # This is g(-k)
            if g2 > i:
                # No second term for this k
                pass
            else:
                total += sign * p[i - g2]
            
            k += 1
        p[i] = total
    return p[n]

# count_partitions_euler(50) = 204226
# Much faster than DP for large n when only p(n) is needed

4. Iterative Generation with O(1) Amortized Time (RuleAsc)

For exhaustive generation where performance matters, the iterative RuleAsc algorithm generates each partition from the previous one by manipulating an array in place. It is the standard for n > 30 and is used in libraries like SageMath.

def partitions_rule_asc(n: int):
    """
    Generate partitions of n in ascending order using RuleAsc (Knuth).
    Yields partitions as lists with non-decreasing order.
    Amortized O(1) time per partition, O(n) space.
    """
    if n == 0:
        yield []
        return

    # a holds the current partition, k is index of last part
    a = [0] * (n + 1)
    k = 1
    a[0] = 0
    a[1] = n

    while k != 0:
        x = a[k - 1] + 1
        y = a[k] - 1
        k -= 1

        # Distribute y into parts of size x
        while y >= x:
            a[k] = x
            y -= x
            k += 1
        a[k] = x + y
        # Yield a copy of current partition a[0..k]
        yield a[0:k+1]

# Usage:
# for part in partitions_rule_asc(6):
#     print(part)  # [6], [1,5], [2,4], [1,1,4], [3,3], [1,2,3], ...

Step-by-Step Example

Let us walk through the complete execution for n = 5 using the recursive enumeration approach. The goal is to generate all 7 partitions while enforcing non-increasing order to avoid duplicates like 1+4 and 4+1 being counted separately. We start with remainder = 5 and max_part = 5.

Step 1: Choose first part. The loop tries i = 5 down to 1. First iteration picks i = 5. We recursively call with remainder = 0, max_part = 5. Since remainder is 0, we return [[]], and prepend 5 to get partition [5]. This is the first complete partition.

Step 2: Backtrack and try i = 4. Remainder becomes 1, max_part = 4. In the recursive call, we try parts from min(4,1)=1 down to 1. Only i=1 is valid, leading to remainder 0. This yields suffix [1], giving partition [4, 1]. Step 3: Try i = 3. Remainder = 2, max_part = 3. The recursive call explores i=2 and i=1. For i=2, remainder 0 yields [3, 2]. For i=1, we go deeper: remainder 1 with max_part 1 yields [1], giving [3, 1, 1]. These are the next two partitions.

Continuation for Remaining Branches

Step 4: Try i = 2 at the top level. Remainder = 3, max_part = 2. This branch is more complex. The call with (3, 2) tries i=2: remainder 1 with max_part 2 tries i=1 to get [2, 2, 1]. Then it tries i=1 at the (3,2) level: remainder 2 with max_part 1 must be partitioned as [1,1], yielding [2, 1, 1, 1]. Notice how the max_part constraint forces the suffix to be non-increasing relative to the prefix.

Step 5: Finally, i = 1 at the top level gives remainder 4 with max_part 1. Since only part 1 is allowed, the only way to sum to 4 is [1,1,1,1], resulting in partition [1,1,1,1,1] after prepending the initial 1. The recursion terminates, having explored all branches. The depth-first traversal ensures partitions are generated in lexicographically descending order.

Counting via DP for the same n illustrates the table filling. To compute p(5), we fill dp[i][j] for i=0..5, j=0..5. The final value dp[5][5] = 7 is built from dp[5][4] = 6 plus dp[0][5] = 1 (partitions using a 5). Each cell reuses previously computed subproblems, turning an exponential recursion into O(n^2) work. This table also answers restricted queries like p(5,2)=3, which are the partitions [2,2,1], [2,1,1,1], [1,1,1,1,1].

Complexity Analysis

The complexity of integer partition algorithms depends critically on whether the goal is counting or enumeration. Counting can be done in polynomial time, while enumeration is inherently exponential because the output size itself is exponential. This distinction is the most important factor when selecting an algorithm for production use.

For enumeration algorithms, time complexity is best expressed as O(n * p(n)) or O(p(n)) depending on the output representation. Since p(n) grows as exp(Theta(sqrt(n))), any enumeration algorithm is exponential in n. However, the amortized cost per partition can be O(1) or O(n) with efficient iterative methods. Space complexity for enumeration is O(n) for the current partition plus recursion stack, or O(n * p(n)) if all partitions are stored.

For counting algorithms, the DP table approach runs in O(n*k) time and O(n*k) space, which is O(n^2) when k=n. With space optimization using a 1D array and iterating j outer, space drops to O(n). Euler's pentagonal theorem improves time to O(n * sqrt(n)) because each p(i) requires O(sqrt(i)) pentagonal numbers. This is the fastest known exact method for single p(n) and is used for n up to 10,000+ with big integers.

The choice between O(n^2) DP and O(n sqrt(n)) Euler depends on query patterns. If many queries p(i, k) for varying k are needed, the DP table answers each in O(1) after preprocessing. If only p(n) for a single large n is needed, Euler is superior. For n=1000, DP requires ~1e6 operations, while Euler requires ~1000*31 ≈ 31k operations, a 30x improvement.

Memory considerations also matter. The 2D DP table for n=5000 requires 25 million integers, which at 28 bytes per Python int exceeds 700 MB. The 1D optimization or Euler method reduces this to 5000 integers. In languages with fixed-width integers, overflow becomes an issue: p(200) exceeds 64-bit, requiring arbitrary-precision arithmetic, which adds a log p(n) factor to time complexity.

Variations and Optimizations

Restricted partitions offer significant optimization opportunities. Partitions into distinct parts can be counted with dp[i][j] = dp[i][j-1] + dp[i-j][j-1], where the second term uses j-1 instead of j to prevent reuse. Partitions into odd parts use only odd j. Partitions with exactly k parts satisfy p_k(n) = p_k(n-k) + p_{k-1}(n-1), derived by subtracting 1 from each part or removing a part of size 1. These recurrences reduce the state space and enable faster specialized algorithms.

Memoization with lru_cache transforms the naive exponential recursion into O(n*k) counting without explicit table management. This is ideal for sparse queries where not all dp[i][j] are needed. For enumeration, generating partitions in-place and yielding them avoids storing all p(n) partitions simultaneously, which is essential for large n. Using Python generators or iterative loops prevents out-of-memory errors.

Advanced optimizations include using NumPy or PyPy for DP table loops, applying the Hardy-Ramanujan-Rademacher convergent series for approximate counting with floating point, and using caching of pentagonal numbers. For distinct partitions, the generating function product_{i>=1} (1 + x^i) can be computed via divide-and-conquer polynomial multiplication using FFT, achieving O(n log^2 n) for all q(i) up to n.

Space Optimization Techniques

The classic 1D DP optimization iterates j from 1 to k outer and i from j to n inner, updating dp[i] += dp[i-j]. This reuses the same array because dp[i-j] already includes partitions using j. For Euler, only the last O(sqrt(n)) values are needed for each i, but the full array is typically kept for simplicity. Bitset techniques can be used when counting modulo a small number or checking existence.

Parallel and Approximate Variants

Enumeration is embarrassingly parallel: different first-part choices correspond to independent subtrees. A parallel implementation can assign branches i = n, n-1, ... to different threads. For approximate counting of huge n where exact p(n) has thousands of digits, the Hardy-Ramanujan asymptotic or the Rademacher series truncated to O(sqrt(n)) terms gives high precision with floating-point arithmetic, useful for cryptography and statistical physics estimates.

Real-World Applications

While integer partitions originate in pure mathematics, they appear surprisingly often in systems engineering. In distributed computing, partitioning an integer corresponds to dividing a total workload, memory budget, or replication factor into unordered groups of tasks. For example, a web server with 10 identical worker threads that must be allocated across 4 request types can be modeled as partitions of 10 into at most 4 parts, where order does not matter because workers are identical.

In databases, partition algorithms help with query optimization for sharding and bucketing. When a table with n rows must be split into buckets for parallel aggregation without caring about bucket order, the number of possible bucket size distributions is p(n). Database optimizers use partition counting to estimate the cardinality of grouping strategies and to generate test cases for partition pruning logic.

Networking and resource allocation use restricted partitions extensively. Allocating bandwidth chunks, dividing packet payloads, or distributing replicas across data centers with capacity constraints maps to partitions into bounded parts. The coin change problem, which is exactly the partition problem with a restricted set of denominations, is used in currency systems, inventory packing, and network packet fragmentation where only certain chunk sizes are allowed.

In scientific computing, integer partitions model integer compositions in quantum physics, where Bose-Einstein statistics count ways to distribute n indistinguishable particles among energy states. The same mathematics appears in music information retrieval for rhythm quantization and in bioinformatics for fragment mass distributions. Understanding the algorithmic trade-offs allows engineers to choose between exact enumeration for small n and asymptotic estimation for large n where exact enumeration is infeasible.

Comparison with Alternatives

Integer partitions are often confused with related combinatorial objects, particularly integer compositions and set partitions. Choosing the wrong model leads to overcounting by orders of magnitude. A composition of n allows order to matter, so 2+1 and 1+2 are distinct, while partitions treat them as identical. Set partitions divide a set of n labeled elements into unlabeled subsets, counted by Bell numbers, which is fundamentally different from dividing the integer n itself.

The coin change problem is a restricted partition problem where allowed parts are limited to a given set of denominations. While the DP recurrence is similar, the state space is smaller and the generating function is product_{c in coins} 1/(1 - x^c). Unlike unrestricted partitions, coin change has polynomial-time counting for fixed denominations but remains NP-hard for optimization variants like minimizing coins.

For enumeration tasks, alternatives include brute-force recursion without ordering constraints followed by deduplication, which is exponentially wasteful, and using integer composition generation with sorting and set insertion to remove duplicates, which adds O(p(n) * n log n) overhead. Direct partition generation via RuleAsc or recursive max_part is always superior for partition-specific tasks.

In practice, if order matters for your application, you need compositions, not partitions. If elements are distinguishable, you need set partitions. The key diagnostic is to ask: does swapping two summands create a distinct configuration? If yes, use compositions; if no, use partitions. For web server load balancing with identical workers, partitions are correct; for request sequences where order matters, compositions are needed.

Common Mistakes and Best Practices

A frequent mistake is generating partitions without enforcing non-increasing or non-decreasing order, leading to duplicate counting of permutations. For example, a naive recursion that tries all i from 1 to n without a max_part limit will generate both [2,1] and [1,2] as separate results, counting compositions instead of partitions. Always pass and enforce a max_part or min_part bound.

Another pitfall is attempting to store all partitions for large n. Since p(100) is 190 million, storing them as lists of integers would require tens of gigabytes and crash most systems. Best practice is to use generators that yield one partition at a time and process it streaming, or to count without enumerating. If you must store counts, use Python's arbitrary-precision integers or modulo arithmetic to avoid overflow, and consider array('I') or numpy for memory efficiency.

Recursion depth is a subtle issue. The deepest recursion path for partitions of n is n (all ones), which exceeds Python's default recursion limit of 1000 when n > 1000. Iterative algorithms like RuleAsc or explicit stack simulation avoid this. If using recursion, increase sys.setrecursionlimit or convert to iterative DP. Additionally, naive recursion without memoization recomputes the same subproblems exponentially many times; always memoize for counting.

Best Practices Checklist

• Enforce ordering: Always constrain next part <= previous part to ensure uniqueness.
• Choose counting vs enumeration: Never enumerate when you only need p(n); use Euler or DP.
• Use generators: Yield partitions one by one for n > 30 to save memory.
• Optimize space: Use 1D DP array when only the final count is needed.
• Handle big integers: Expect p(n) to exceed 64-bit for n > 200; use Python int or big integer libraries.
• Test small n: Validate against known values: p(5)=7, p(6)=11, p(10)=42, p(20)=627.
• Profile before parallelizing: Enumeration parallelizes well, but counting DP is memory-bound.

Finally, be careful with off-by-one errors in DP base cases. dp[0][j] should be 1 for all j (one way to make sum 0), and dp[i][0] should be 0 for i > 0. Incorrect base cases silently produce wrong counts that are hard to debug. Write unit tests that compare DP results against Euler's recurrence for n up to 100 to catch such errors early.

Interview Questions

Integer partition problems are popular in technical interviews because they test recursion, dynamic programming, and combinatorial reasoning in a single problem. Below are common questions with solution sketches and what interviewers look for.

Q1: Generate all partitions of n. What is the time complexity?

Expected answer: Provide a recursive solution with max_part parameter as shown in Implementation section, or an iterative RuleAsc variant. Discuss that time is O(n * p(n)) to generate and output, and O(p(n)) amortized if counting operations only. Mention that p(n) is exponential, so enumeration is only feasible for n <= 30-40. Follow-up: How would you modify it to generate partitions into distinct parts? Answer: Change recursive call to use max_part = i-1 instead of i.

Q2: Count the number of partitions of n without enumerating them. Optimize for large n.

Expected answer: Present the DP recurrence p(n,k) = p(n,k-1) + p(n-k,k) with O(n^2) time and O(n) space optimization. For bonus points, present Euler's pentagonal theorem for O(n sqrt n) time and explain pentagonal numbers g(k)=k(3k-1)/2. Interviewers look for recognition that counting does not require enumeration and for knowledge of the more efficient Euler method. Be prepared to code the 1D DP loop: dp[0]=1; for j in 1..n: for i in j..n: dp[i]+=dp[i-j].

Q3: What is the difference between partitions and compositions? How many compositions does n have?

Expected answer: Partitions ignore order, compositions consider order distinct. Number of compositions of n is 2^(n-1), because there are n-1 gaps between n ones, each gap can be either a cut or not. This can be proved by stars and bars. A strong candidate will also mention the generating function difference and give an example for n=4: 8 compositions vs 5 partitions. This tests conceptual clarity.

Q4: Count partitions of n into exactly k parts. How does this relate to partitions with largest part k?

Expected answer: Use DP with p_k(n) = p_k(n-k) + p_{k-1}(n-1) or conjugate via Ferrers diagram: number of partitions of n into exactly k parts equals number of partitions of n with largest part k, and equals number of partitions of n with at most k parts minus those with at most k-1 parts. Provide O(n*k) DP. The conjugacy argument using Ferrers diagram transposition is a key insight interviewers want to hear.

Q5: How would you handle n=1000 where p(n) has 31 digits and enumeration is impossible?

Expected answer: Discuss that enumeration is infeasible, so use counting with big integers or modulo, or use Hardy-Ramanujan asymptotic for approximation: p(n) ~ exp(pi*sqrt(2n/3))/(4n*sqrt(3)). Mention using Euler's recurrence with Python's arbitrary-precision ints for exact value, and that DP table would be 1e6 entries, which is feasible. For testing, use memoization and iterative methods to avoid recursion depth issues. This tests practical judgment about exponential blowup and big integers.

Preparing for these questions involves practicing both the recursive generation pattern and the DP counting pattern until they can be written bug-free on a whiteboard. Focus on explaining the recurrence derivation, not just memorizing code, and be ready to analyze space-time trade-offs for each variant.