Hello guys

I have am interesting recursion problem for you. I am interested in an SML solution but feel free to drop a recursive C++ version.

Let's say we have the sum s and I want to generate all the possibilities in which I can write this sum in as the sum of n terms. Let's take an example:

s=4 and n=3 then I want to generate a list that looks like this:

[[0,0,4],[0,1,3],[0,2,2],[0,3,1],[0,4,0],[1,0,3],[1,1,2],[1,2,1],[1,3,0],[2,0,2],

[2,1,1],[2,2,0],[3,0,1],[3,1,0],[4,0,0]]

basically s is the sum and n the number of terms I can use to compute the sum.

Please let me know what ideas you have.

I have am interesting recursion problem for you. I am interested in an SML solution but feel free to drop a recursive C++ version.

Let's say we have the sum s and I want to generate all the possibilities in which I can write this sum in as the sum of n terms. Let's take an example:

s=4 and n=3 then I want to generate a list that looks like this:

[[0,0,4],[0,1,3],[0,2,2],[0,3,1],[0,4,0],[1,0,3],[1,1,2],[1,2,1],[1,3,0],[2,0,2],

[2,1,1],[2,2,0],[3,0,1],[3,1,0],[4,0,0]]

basically s is the sum and n the number of terms I can use to compute the sum.

Please let me know what ideas you have.

I'll see if I can get a program working, and then I'll give some pointers. :)

EDIT: Does it have to be recursive??

EDIT: Does it have to be recursive??

Last edited on

well in SML it can't be but recursive. I suppose in C++ it can also be done in an iterative way. I don't particularly mind.

It would be rather easy to construct a recursive version, but how efficient does the solution have to be?

Last edited on

Topic archived. No new replies allowed.