This algorithmic question is from Google Code Jam 2009. problem we need to solve in this question is that, Given a number in given base, can we find number of summands for given number provided that numbers in the a same column in summation should not be similar to one another.
So Basic answer comes in to mind is , first find all possible summations that can represent different sums of the given number. we will start with the smallest number lets say 1, and add the rest to get the required number. As an example if we take number 11 then 1 + 10 = 11, and we try to find different ways in which 1 can be written. but there is only one way. there for we are going to find different ways in which 10 can be written. we can not take 1 again bcoz it is already there in the solution. So Here comes my problem, how do we find out all the different ways of writing this number.
No comments:
Post a Comment