Integer Partition Algorithm

Problem

The integers can be partitioned by representing a number as the sum of positive integers (ignoring order). The task is to compute all possible integer partitions of a given number n.

For a number n = 5, the integer partitions are:

5
4 + 1
3 + 2
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Input:  
n = 4  
Output:  
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]  
Explanation:  
Partitions of 4 are:  
- 4  
- 3+1  
- 2+2  
- 2+1+1  
- 1+1+1+1

Example 2

1
2
3
4
5
6
7
8
9


Input:  
n = 3  
Output:  
[[3], [2, 1], [1, 1, 1]]  
Explanation: 
Partitions of 3 are:  
- 3  
- 2+1  
- 1+1+1

Solution

Method 1 - Recursion

One important observation is that permutations of the summands in a partition do not create new, distinct partitions. For example, both 2+3 and 3+2 represent the same partition of 5. Therefore, to find all unique partitions of an integer N, we need to ensure our algorithm respects this rule.

While generating functions can mathematically solve this problem (refer to Wikipedia’s entry for details), implementing such functions algorithmically is complex. A simpler approach is to use a recursive divide-and-conquer method. This means breaking the problem into smaller subproblems recursively to find all possible partitions.

Divide-and-Conquer Intuition

To find all partitions for a number N:

First, split the solutions into two groups:
- Group A: Includes partitions that use the number N itself at least once (this group has only one solution: N).
- Group B: Partitions that exclude N, which reduces the problem to finding all partitions of N using integers smaller than N (subset {1, 2, ..., N-1}).
Recursively apply this process to Group B, splitting it into:
- Subgroup A: Solutions that include the next largest number (N-1).
- Subgroup B: Solutions that exclude N-1.

By using this recursive strategy, we can systematically generate all unique partitions by progressing from the largest number to smaller numbers.

Recursive Base Cases

For the recursive function:

Sum = 0: If the target sum is exhausted (sum = 0), this marks a valid partition. We return 1 for this case since a valid partition is found.
Sum < 0: If the current sum becomes negative (sum < 0), the partition is invalid, and we return 0 to signify no solution.
Largest number available = 0: If the largest available number becomes zero, there are no integers left to form the partition, and we return 0.

Algorithm Description and Variables

The recursive function is structured as follows:

Input 1: sum - The target sum we are trying to partition.
Input 2: largestNumber - The largest number allowed in a partition for the current recursive call.
Using these variables, the function dynamically adjusts the range of integers it can use to form partitions, ensuring uniqueness by keeping the numbers in progressively non-increasing order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution {
public:
    int helper(int sum, int largestNumber) {
        // Base Cases
        if (sum == 0)
            return 1; // Found one valid partition
        if (sum < 0 || largestNumber == 0)
            return 0; // No valid partition

        // Divide-and-Conquer: Include the largestNumber OR exclude it
        int includeLargest = helper(sum - largestNumber, largestNumber);
        int excludeLargest = helper(sum, largestNumber - 1);

        return includeLargest + excludeLargest; // Combine both groups
    }

    int integerPartition(int n) {
        return helper(n, n); // Call the helper function
    }
};

// Example usage
int main() {
    Solution solution;
    int n = 5;
    cout << "Number of partitions for " << n << ": " << solution.integerPartition(n) << endl;
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
    private int helper(int sum, int largestNumber) {
        // Base cases
        if (sum == 0)
            return 1; // Found one valid partition
        if (sum < 0 || largestNumber == 0)
            return 0; // No valid partition

        // Divide-and-Conquer: Include the largestNumber OR exclude it
        int includeLargest = helper(sum - largestNumber, largestNumber);
        int excludeLargest = helper(sum, largestNumber - 1);

        return includeLargest + excludeLargest; // Combine both groups
    }

    public int integerPartition(int n) {
        return helper(n, n); // Start the recursive partitioning
    }

    // Example usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 5;
        System.out.println("Number of partitions for " + n + ": " + solution.integerPartition(n));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def integerPartition(self, n):
        # Recursive function to compute partitions
        def helper(sum, largestNumber):
            # Base Cases
            if sum == 0:
                return 1  # Found one valid partition
            if sum < 0 or largestNumber == 0:
                return 0  # No valid partition
            
            # Divide-and-Conquer: Include the largestNumber OR exclude it
            includeLargest = helper(sum - largestNumber, largestNumber)
            excludeLargest = helper(sum, largestNumber - 1)
            
            return includeLargest + excludeLargest  # Combine both groups

        # Call the helper function
        return helper(n, n)

# Example usage:
solution = Solution()
n = 5
print(f"Number of partitions for {n}: {solution.integerPartition(n)}")

Complexity

⏰ Time complexity: O(2^n) for given n. The naive approach splits the problem into two recursive branches at each step (largestNumber being included or excluded), resulting in exponential growth.
🧺 Space complexity: O(n). Each recursive call consumes stack space. In the worst case (with no base cases reached), the recursion depth equals n.

Method 2 - Using Top-down DP approach using memoization

Memoization optimises the naive recursive solution by storing previously computed results in a hash map or table. This avoids redundant recursive calls and significantly reduces the time complexity.

Here is the approach:

Memoization Table: Use a 2D data structure (memo[sum][largestNumber]) to store results:
- sum is the remaining sum we want to partition.
- largestNumber is the largest number currently allowed in the partition.
Recursive Computation: For each (sum, largestNumber), compute the partitions by:
- Including the current largest number.
- Excluding the current largest number.
Base Cases: Same as the naive recursive solution:
- If sum == 0, a valid partition is found → Return 1.
- If sum < 0 or largestNumber == 0, no valid partition → Return 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


class Solution {
private:
    unordered_map<string, int> memo; // Memoization dictionary

    // Private helper function with memoization
    int helper(int sum, int largestNumber) {
        // Create memoization key
        string key = to_string(sum) + "," + to_string(largestNumber);
        if (memo.find(key) != memo.end())
            return memo[key];

        // Base cases
        if (sum == 0)
            return 1; // Found a valid partition
        if (sum < 0 || largestNumber == 0)
            return 0; // No valid partition

        // Recursive computation with memoization
        int includeLargest = helper(sum - largestNumber, largestNumber);
        int excludeLargest = helper(sum, largestNumber - 1);

        memo[key] = includeLargest + excludeLargest;
        return memo[key];
    }

public:
    // Public method to start partitioning
    int integerPartition(int n) {
        return helper(n, n); // Start recursion with the full range
    }
};

// Example usage
int main() {
    Solution solution;
    int n = 5;
    cout << "Number of partitions for " << n << ": " << solution.integerPartition(n) << endl;
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class Solution {
    private Map<String, Integer> memo = new HashMap<>(); // Memoization map

    // Private helper function with memoization
    private int helper(int sum, int largestNumber) {
        // Create memoization key
        String key = sum + "," + largestNumber;
        if (memo.containsKey(key))
            return memo.get(key);

        // Base cases
        if (sum == 0)
            return 1; // Found a valid partition
        if (sum < 0 || largestNumber == 0)
            return 0; // No valid partition

        // Recursive computation with memoization
        int includeLargest = helper(sum - largestNumber, largestNumber);
        int excludeLargest = helper(sum, largestNumber - 1);

        memo.put(key, includeLargest + excludeLargest);
        return memo.get(key);
    }

    // Public method to start partitioning
    public int integerPartition(int n) {
        return helper(n, n); // Start recursion with the full range
    }

    // Example usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 5;
        System.out.println("Number of partitions for " + n + ": " + solution.integerPartition(n));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution:
    def integerPartition(self, n):
        # Initialize memo dictionary
        memo = {}

        # Private helper function with memoization
        def helper(sum, largestNumber):
            # Use memoization key for current subproblem
            key = (sum, largestNumber)
            if key in memo:
                return memo[key]

            # Base cases
            if sum == 0:
                return 1  # Found a valid partition
            if sum < 0 or largestNumber == 0:
                return 0  # No valid partition

            # Recursive computation with memoization
            includeLargest = helper(sum - largestNumber, largestNumber)
            excludeLargest = helper(sum, largestNumber - 1)

            memo[key] = includeLargest + excludeLargest
            return memo[key]

        return helper(n, n)

# Example usage
solution = Solution()
n = 5
print(f"Number of partitions for {n}: {solution.integerPartition(n)}")

Complexity

⏰ Time complexity: O(n^2). Memoization reduces redundant recursive calls to n x n possible combinations of (sum, largestNumber).
🧺 Space complexity: O(n^2) for using the memoization table.

Method 3 - Using bottom-up DP

A bottom-up dynamic programming approach for the integer partition problem involves constructing a table (DP array) where:

Each column represents the largest number allowed in the partition at that step.
Each row represents the target sum (i) we want to partition.

This approach eliminates recursion, focusing on iteratively solving smaller subproblems and combining their solutions to form the final result.

Steps

DP Table Initialization:
- Set up the table with the base cases:
  - When the column (largest number) is 0, there are no valid partitions → table[i][0] = 0.
  - When the row (target sum) is 0, the sum is already achieved → table[0][j] = 1 for all j.
DP Transition:
- Traverse the table row by row and column by column:
  - Excluding largest number: Use the value from the column immediately left (table[i][j-1]).
  - Including largest number: Check if it’s valid (only if i-j >= 0) and add table[i-j][j].
Boundary Handling:
- Ensure that i-j >= 0 before accessing table[i-j][j]. If not, skip adding from the reduced sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


class Solution {
public:
    int integerPartition(int sum, int largestNumber) {
        // Initialize DP table
        vector<vector<int>> dp(sum + 1, vector<int>(largestNumber + 1, 0));

        // Base cases
        for (int j = 0; j <= largestNumber; j++) {
            dp[0][j] = 1; // There is one way to partition sum=0
        }

        for (int i = 1; i <= sum; i++) {
            for (int j = 1; j <= largestNumber; j++) {
                dp[i][j] = dp[i][j - 1]; // Exclude the current largest number
                if (i - j >= 0) {
                    dp[i][j] += dp[i - j][j]; // Include the current largest number
                }
            }
        }

        return dp[sum][largestNumber];
    }
};

// Example usage
int main() {
    Solution solution;
    int sum = 100;
    int largestNumber = 99;
    cout << "Number of partitions for sum=" << sum << " with largestNumber=" 
        << largestNumber << ": " << solution.integerPartition(sum, largestNumber) << endl;
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


public class Solution {
    public int integerPartition(int sum, int largestNumber) {
        // Initialize DP table
        int[][] dp = new int[sum + 1][largestNumber + 1];

        // Base cases
        for (int j = 0; j <= largestNumber; j++) {
            dp[0][j] = 1; // There is one way to partition sum=0
        }

        for (int i = 1; i <= sum; i++) {
            for (int j = 1; j <= largestNumber; j++) {
                dp[i][j] = dp[i][j - 1]; // Exclude the current largest number
                if (i - j >= 0) {
                    dp[i][j] += dp[i - j][j]; // Include the current largest number
                }
            }
        }

        return dp[sum][largestNumber];
    }

    // Example usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        int sum = 100;
        int largestNumber = 99;
        System.out.println(
            "Number of partitions for sum=" + sum + " with largestNumber=" + largestNumber + ": " 
            + solution.integerPartition(sum, largestNumber));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
    def integerPartition(self, sum, largestNumber):
        # Initialize DP table
        dp = [[0 for _ in range(largestNumber + 1)] for _ in range(sum + 1)]

        # Base cases
        for i in range(largestNumber + 1):
            dp[0][i] = 1  # There is one way to partition sum=0

        for i in range(1, sum + 1):
            for j in range(1, largestNumber + 1):
                dp[i][j] = dp[i][j - 1]  # Exclude the current largest number
                if i - j >= 0:
                    dp[i][j] += dp[i - j][j]  # Include the current largest number

        return dp[sum][largestNumber]

# Example usage
solution = Solution()
sum = 100
largestNumber = 99
print(f"Number of partitions for sum={sum} with largestNumber={largestNumber}: {solution.integerPartition(sum, largestNumber)}")

Complexity

⏰ Time complexity: O(n^2). The table is filled iteratively across sum × largestNumber cells.
🧺 Space complexity: O(n^2). The table requires storage proportional to its dimensions.

Problem#

Examples#

Example 1#

Example 2#

Solution#

Method 1 - Recursion#

Divide-and-Conquer Intuition#

Recursive Base Cases#

Algorithm Description and Variables#

Code#

Complexity#

Method 2 - Using Top-down DP approach using memoization#

Code#

Complexity#

Method 3 - Using bottom-up DP#

Steps#

Code#

Complexity#

Problem

Examples

Example 1

Example 2

Solution

Method 1 - Recursion

Divide-and-Conquer Intuition

Recursive Base Cases

Algorithm Description and Variables

Code

Complexity

Method 2 - Using Top-down DP approach using memoization

Code

Complexity

Method 3 - Using bottom-up DP

Steps

Code

Complexity