Print all unique integer partitions given an integer as input

algorithm, decomposition, numbers, partition-problem, recursion

Solution

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

Problem

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!!

Original source