This doesn't get you the path itself, it only gets you the length of the path. Think of it like this: the decision version question is: Is there a path of len

This doesn't get you the path itself, it only gets you the length of the path. Think of it like this: the decision version question is: Is there a path of length k that hits all of the cities? The algorithm just has to answer yes/no, it doesn't have to give you the path itself. So you can use binary search to repeatedly ask whether there is a path with length less than k, and home in on the optimal length. You still don't know what the path is. We assume it would be difficult for the algorithm to make this determination without having actually discovered the path, but the problem doesn't require that it output any such path. Edit: This is wrong, ColinWright details how to get the actual path from just knowing the length