Here's an interview question I was asked that has been fucking with my brain: Suppose you have a long bookshelf and you have some array of books that you can put onto the bookshelf. b[i] represents the width of book i, and the bookshelf has a set length (100 inches). How do you choose books such that the amount of empty space left in the bookshelf is minimized? For example, if the bookshelf has 30 inches long and you have books that are [2,10,5,17] inches wide, then the best you can do is 2+10+17 = 29.
Is there no better way than to run through all subsets and just keep track of a max sum <= bookshelf width? Doesn't it feel like this can be solved with dp? The issue is that you have to keep all possible combination sums up to index i, because you don't always want to just keep the maximum, so that also results in O(2n)