For a number partition of width x, is there a fast way to calculate offset k without recurring/calculating the previous possibilities?
A number partition implies to have the left slot value greater or equal to the one we are looking at.
e.g: 6,5,5,4 works
but
6,5,4,5 doesn't because the 2nd 5 is greater than 4. wiki article
So the logic is to get from the highest numbers combination to the lowest possible values combination.
For example, for an array of length 5 with a maximum value of 6, which sum is 21, gives:
6,6,6,2,1 //offset 0
6,6,5,3,1 //offset 1
6,6,5,2,2
6,6,4,4,1
6,6,4,3,2
6,6,3,3,3
6,5,5,4,1
6,5,5,3,2
6,5,4,4,2 //offset 8
6,5,4,3,3
6,4,4,4,3
5,5,5,5,1
5,5,5,4,2
5,5,5,3,3
5,5,4,4,3
5,4,4,4,4 //offset 15
There are 16 solutions for these parameters.
If I am interested in knowing what the offset 8 looks like, do I have to calculate all the previous solutions first or is there an existing formula?
Thanks