It fails for this test case.
I think your else block inside the loop is buggy. Check that.
Saurabh, I think now you can make your way. By the way, you can implement a recursive procedure (as suggested by above, for possible subset generation), which easily solves the problem, and them memoize it for further improvement. Infact, nonmemoized version is also accepeted here. :) answered 26 Jan '15, 12:39
Okay, You are right, my solution is giving WA for the above case. Anyway, isn't there a DP solution for this problem. I mean subset generation is working just because n<=20, what if it would have been greater ?
(26 Jan '15, 16:11)
1
I think you can implement a topdown DP by memoizing the recursive solution. For bottom up, one can think of in terms of knapsack, but as range of bookshelf is large, you have to implement a space efficient version.
(26 Jan '15, 19:26)

@saurabh: Prerequisites: Subset generation Now what you need to do is generate all the possible combinations of the books and store the minimum space left. One condition that is needed to care if all the sizes of books are greater than capacity then answer will be capacity itself. Hope you get it! answered 26 Jan '15, 12:29

Simply just generate all subsets (using bitmasking) and find the subset with largest sum which is also less than or equal to the self size. my solution answered 26 Jan '15, 15:14

Just wanted to give this fact there, I did the question both ways(generating subsets), you may look here. The first way has recursion which takes just 0.04 sec while the sec takes 0.46 sec and it has no function calls. The use of pow() function is basically the cause of such big time gap. Although I thought recursion can once give TLE because of calls. answered 29 Jan '15, 20:18
