4 ms·
The lists L and M have to be O(2^N) in size, where N is the target sum. I fail to see how this is any faster. In fact I think it's a little slower, if N is the
by H8crilA 5y ago
The lists L and M have to be O(2^N) in size, where N is the target sum. I fail to see how this is any faster. In fact I think it's a little slower, if N is the target sum and M is the number of toys this algorithm runs in O(2^N * M * log(M))
- nroets 5y agoNo. Small n in only 21. You split the toys in a set of 10 and a set of 11. What I'm really describing is the Meet In The Middle algorithm: https://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-middle https://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-m...