Print all unique integer partitions given an integer as input

Question

I was solving a programming exercise and came across a problem over which I am not able to satisfactorily find a solution. The problem goes as follows:

Print all unique integer partitions given an integer as input.
Integer partition is a way of writing n as a sum of positive integers.

for ex: Input=4 then output should be Output=

 1 1 1 1
 1 1 2
 2 2
 1 3
 4

How should I think about solving this problem? I was wondering about using recursion. Can anyone provide me an algorithm for this question? Or a hint towards solution. any explanation for such kind of problems is welcome. (I am a beginner in programming world) Thank you!!

Answer 1

I would approach it this way:

First, generalize the problem. You can define a function

printPartitions(int target, int maxValue, string suffix)

with the specification:

Print all integer partitions of target, followed by suffix, such that each value in the partition is at most maxValue

Note that there is always at least 1 solution (provided both target and maxValue are positive), which is all 1s.

---

You can use this method recursively. So lets first think about the base case:

printPartitions(0, maxValue, suffix)

should simply print suffix.

---

If target is not 0, you have to options: either use maxValue or not (if maxValue > target there is only one option: don't use it). If you don't use it, you should lower maxValue by 1.

That is:

if (maxValue <= target)
 printPartitions(target-maxValue, maxValue, maxValue + suffix);
if (maxValue > 1)
 printPartitions(target, maxValue-1, suffix);

---

Combining this all leads to a relatively simple method (coded in Java here and I reordered the statements a little to obtain the very same order as you described):

void printPartitions(int target, int maxValue, String suffix) {
 if (target == 0)
 System.out.println(suffix);
 else {
 if (maxValue > 1)
 printPartitions(target, maxValue-1, suffix);
 if (maxValue <= target)
 printPartitions(target-maxValue, maxValue, maxValue + " " + suffix);
 }
}

You can simply call this as

printPartitions(4, 4, "");

which outputs

1 1 1 1 
1 1 2 
2 2 
1 3 
4 

---

You can also choose to first create a list of all solutions and only print afterwards, like this:

function createPartitions(target, maxValue, suffix, partitions) {
 if (target == 0) {
 partitions.push(suffix);
 } else {
 if (maxValue > 1)
 createPartitions(target, maxValue-1, suffix, partitions);
 if (maxValue <= target)
 createPartitions(target-maxValue, maxValue, [maxValue, ...suffix], partitions);
 }
}
const partitions = [];
createPartitions(4, 4, [], partitions);
console.log(partitions);

• Eftekhari: How to work around this method to fill List<int[]> partitions = new ArrayList<>();?
• Vincent van der Weele: @Eftekhari 1) change the type of suffix from String to int[], 2) change maxValue + " " suffix to something adding maxValue to the front of suffix, 3) add a function parameter List<int[]> partitions and pass the empty list on the initial call, 4) change System.out.println(suffix) to partitions.add(suffix)
• Eftekhari: It didn't work. Arrays are bigger than number. Would you please try it to make sure it works?
• Vincent van der Weele: @Eftekhari I added a runnable javascript snippet to the answer now. You can do something similar in Java.

Answer 2

This is loosely derived from Heuster's approach.

Firstly, note that the last numbers of the output are 1,2,2,3,4. If the last number is 2, the 2nd last numbers are 1,2. This tells me that it might be a good idea have a recursive function with a for-loop generating the string from the back.

The code itself is pretty straight-forward:

• Loop from 1 to target, prepending the variable to the suffix, subtracting it from target and recursing.
• Also note that each generated string is sorted (which implicitly avoids duplication of output). We get it sorted by simply passing in the last-generated number and looping no further than that number.

Code:

private void printPartitions(int target, int max, String suffix)
{
 if (target == 0)
 System.out.println(suffix);
 else
 {
 for (int i = 1; i <= max && i <= target; i++)
 printPartitions(target - i, i, i + " " + suffix);
 }
}

Caller function:

public void printPartitions(int target)
{
 printPartitions(target, target, "");
}

• Vincent van der Weele: Yep, this way you get rid of the deep recursion and the code is even shorter :) I found the other easier to explain though :)
• coder_15: what is the time complexity of above solution?

Answer 3

The process to enumerate the integer partitions of a number n is recursive. There is a single partition of 0, the empty set (). There is a single partition of 1, the set (1). There are two partitions of 2, the sets (1 1) and (2). There are three partitions of 3, the sets (1 1 1), (1 2) and (3). There are five partitions of 4, the sets (1 1 1 1), (1 1 2), (1 3), (2 2), and (4). There are seven partitions of 5, the sets (1 1 1 1 1), (1 1 1 2), (1 2 2), (1 1 3), (1 4), (2 3) and (5). And so on. In each case, the next-larger set of partitions is determined by adding each integer x less than or equal to n to all the sets formed by the partition of n − x, eliminating any duplicates.

I give code in several languages at my blog. For example, here is my solution in Scheme:

(define (set-cons x xs)
 (if (member x xs) xs
 (cons x xs)))
(define (parts n)
 (if (zero? n) (list (list))
 (let ((xs (list)))
 (do ((x 1 (+ x 1))) ((= x n) (cons (list n) xs))
 (do ((yss (parts (- n x)) (cdr yss))) ((null? yss))
 (set! xs (set-cons (sort < (cons x (car yss))) xs)))))))
> (parts 0)
(())
> (parts 1)
((1))
> (parts 2)
((2) (1 1))
> (parts 3)
((3) (1 1 1) (1 2))
> (parts 4)
((4) (2 2) (1 1 2) (1 1 1 1) (1 3))
> (parts 5)
((5) (2 3) (1 1 3) (1 1 1 1 1) (1 1 1 2) (1 2 2) (1 4))
> (parts 6)
((6) (3 3) (2 2 2) (2 4) (1 1 4) (1 1 2 2) (1 1 1 1 2)
 ((1 1 1 1 1 1) (1 1 1 3) (1 2 3) (1 5))

Answer 4

here is an algorithm. let me know what you think. tested on python3

def partition(A):
 table = [[[1]]] + [None]*(A-1)
 for i in range(1,A):
 table[i] = [[i+1]]
 for k in range(i):
 table[i].extend([[i-k]+l for l in table[k] if i-k >= l[0]])
 return table[-1]
def print_partition(A):
 for i in reversed(partition(A)): print(*i)

• Sidharth Samant: Can this be modified to include only the partitions with distinct parts?
• rnbguy: what do you mean by distinct parts? examples?
• Sidharth Samant: The partitions for 4 are [4], [3,1], [2,2] and [1,1,1,1]. But the partitions with distinct parts are [4] and [3,1], because the others contain duplicates. See the section about odd parts and distinct parts -> en.m.wikipedia.org/wiki/Partition_(number_theory)
• rnbguy: yes sure. just change i-k >= l[0] to i-k > l[0] :)
• rnbguy: just to give you idea, my code uses dynamic programming.