Time complexity in the 'meet in the middle' example

[alessandro-bugatti]

I'm translating your book in Italian and I have a doubt. At the end of chapter 5, you state that "it is possible to check in $O(2^{n/2})$ time if the sum $x$ can be created from $S_A$ and $S_B$". Maybe I'm wrong, but I think that this could be possibile only if both $S_A and $S_B are sorted, as it seems in the example. If I'm wrong, could you explain more about how to achieve that complexity? Otherwise, could you add the assumption about sorting?

[pllk]

That's a good point. We can do this in $O(2^{n/2})$ time but it's not trivial, so it should be explained in the text. The trick is to generate the lists so that they are already sorted using a merge-like technique.