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