Would be great to get at least a glimpse of an understanding about why the algorithm does the enumeration in the first place.

Surely it cannot be necessary for the complexity result?!

It's just irrelevant for big-O complexity what happens for instances below a constant threshold, so the algorithm uses the simplest approach and moves on. If you have an exponential-time algorithm that's faster than brute force for small instances, you can use that and get a faster overall runtime at the same big-O complexity. If you can lower the switchover threshold, ditto. It's a bit weird to dismiss the subexponential algorithm just because it's leaving an obvious optimization on the table... it can only get faster from here.