On Jul 13, 1:13 am, Debajyoti Sarma <[email protected]> wrote: > @Gene > Please explain the recursive function and the first if condition ....i > m not getting it.
We are recursively decomposing the problem of constructing a partition of the number N into M summands, where we require that no summand is less than Min. We build up the current partition in the buffer buf by adding summands one at a time using the buffer pointer bp. If N = M = 0, then we have we have zero summands left to discover, and these must sum to zero. This is the easy base case! Whatever summands are already in the buffer are the answer, so we just print them. Otherwise we need to worry about the case where we still have summands to discover, which is M>0. How to find them? In sequence, we pick each possible summand: I = Min, Min + 1, Min+2, ... N. In each case, we add this new summand to the buffer with buf[bp++]=I and recur to solve the remaining smaller problem. The smaller problem is to partition N - I into M - 1 summands. In order to avoid repeats, we require that no summand added to the buffer after this one smaller. When we have finished recurring, we remove the summand I from the buffer with "bp--". This prepares us for the next try. Note that this code does much unnecessary searching. Making the second "if" condition stronger can help. For example, when N > M * Min, there is no way that futher recursion is going to find another summand, so you might as well return immediately. Limiting a search in this manner is sometimes called a "cut." . -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
