I have got this problem from my computer teacher that for a number N, is it to be displayed in the form of sums. Like for example 4 can be displayed as [4],[3+1],[2+2],[2+1+1],[1+1+1+1]. I need to write a program to display these partitions for any number N.

I don't have the logic clear and this is the program that I got from Integer Partition Program

I did the dry run of this program in pen and paper and the outputs seem to be correct, but I am not quite following the logic of this program. If some one could help me out in understanding the logic of this problem, it would be very kind of you.

Regards,

Ranajoy

- 1

`partition(int n, int max, String prefix)`method. It partitions a number n into terms, with each term being no greater than max.

At first we say "partition 4, and I want no term to be greater than 4".

The for-loop then does the following:

Partition 0, with no term being greater than 4, and prefix every solution with

`" 4"`:

`" 4"`

Partition 1, with no term being greater than 3, and prefix every solution with

`" 3"`:

`" 3 1"`

Partition 2, with no term being greater than 2, and prefix every solution with

`" 2"`:

`" 2 2", "2 1 1"`

Partition 3, with no term being greater than 1, and prefix every solution with

`" 1"`:

`" 1 1 1 1"`

The trick in recursion is to just trace 1 method call, and not to trace deeper recursive calls. Just assume that they "magically work", and see how their calls are combined to achieve what you want.

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

If I asked you to write down all sums that total 5, what steps would you take in your mind? Describe it in your own words first. Don't think about code.

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

5 is equal to 5, so print 5 then reduce n by 1 (n--)

4 is not equal to 5, there for sum = 4 + arr[0] = 5, and sum == 5, therefore print 4 + 1,

(n--)

3 is not equal to 5, there for sum = 3 + arr[0] = 4 which is not equal to 5, so, sum += arr[0] which is equal to 5 therefore print 3 + 1 + 1

Again as the parsing of the numbers of the loop is not completed, sum = 3 + arr[1] which is equal to 5 thus print 3 + 2 and as 3 + arr[2] or 3+arr[3] is higher than 5 so, break the loop

This is the way I was thinking of solving this problem. But I wasn't able to create a valid algorithm for progression.

I'm asking you now to write down all partitions of 5. For each partition, explain how you got there. This should not be a lot of work, because there are only 7 decompositions.

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

5 (We began with 5)

4+1 (4 is before 5 and adding 1 to 4 gives 5)

3+2 (3 is before 4 and adding 2 to it gives 5)

3+1+1 (2 can also be written as 1+1)

2+2+1 (2 is before 3 and adding 3 to it gives 5 but as 3+2 already exists breaking 3 to 2+1)

2+1+1+1 (Splitting last 2 to 1+1)

1+1+1+1+1 (Splitting the remaining 2 to 1+1)

I hope you asked for this, if not sorry. This is what I make of "I'm asking you now to write down all partitions of 5. For each partition, explain how you got there."

- 1

Now, do you notice a pattern? You saw that getting the decomposition 3 + 1 + 1, was actually the same as applying the partition to 2, in the decomposition 3 + 2.

So you actually performing a partition within a partition? This is recursion!

The pattern here is that for each integer from 5 to 1, you print that integer for each partition of the remainder, right? In pseudocode:

If you understand this pseudocode, and how we got there, then try to realize it as actual Java code.

Don't worry about ignoring decompositions like 1 + 3 + 1 yet, we'll deal with that later.

- 1

Lists are actually very very useful, I couldn't think of writing applications without them. I think it's best to learn about them as soon as possible.

For now, initialize a list like this:

Add a partition to the list like this:

You can iterate over all partitions within a list like this: