You are given two positive integers, sum and count. Consider all possible ways to express sum as a sum of exactly count positive integers. Two ways are considered equal if we can obtain one from the other by changing the order of the summed numbers. For example, 8=3+2+1+1+1 is the same as 8=1+3+1+2+1, but not the same as 8=3+2+2+1. Thus we will only be interested in such summations where the summed integers are in non-increasing order.
For example, if sum=8 and count=3, the possible ways are:
8 = 6+1+1
8 = 3+3+2
8 = 4+2+2
8 = 4+3+1
8 = 5+2+1
We may now order these summations in the following way: Order them according to the first summand in decreasing order. In case of a tie, order them according to the second summand, etc. In general, to compare two summations, look at the first summand where they differ. The one where this summand is larger will be earlier in our order.
For our previous example, the correct order is:
8 = 6+1+1
8 = 5+2+1
8 = 4+3+1
8 = 4+2+2
8 = 3+3+2
You will be given three ints: sum, count and index, where index contains a zero-based index of a summation in the order defined above. Your method should return a String containing that summation in the form "SUM=SUMMAND(1)+...+SUMMAND(count)".
If index is too large to specify a valid summation, return an empty string.
|