This problem can be solved with recursive backtracking approach. The number of tracks on the CD is at most $20$. As we can either take a CD without exceeding the tape length or leave it, there are at most $2^{20}$ choices and in the worst case we have to traverse all of them.
We start traversing from the first CD and continue until we’ve reached the last CD. At each point, we’ll try to take the current CD without exceeding the tape length. If the current CD is taken, we’ll update the current sum and current choices accordingly. When we’ve gone past the last CD, we’ll update the answer and answer choices.
Here’s the implementation in C++
:
Sharing is caring. Share this story in...
Share: Twitter Facebook LinkedIn