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);