What is the difference between exhaustive search & combinatorial search?
My two cents: exhaustive search is also known as brute force search, an approach in which you have no better strategy than to explore the entire search space, testing every possible candidate solution. Two examples were given by @Yuval Filmus. If you are really unlucky, the solution may well be the last candidate explored, or one of the last ones. Therefore, in general exhaustive search is in the worst case linear in the size of the search space to be explored.

On the other hand, combinatorial search instead is a smarter kind of search, which usually exploits one or more pruning strategies to avoid testing all of the possible candidate solutions. In this case, you can safely discard some candidates (depending on the particular algorithm of course) and therefore you can save precious time. An example of combinatorial search is, for instance, branch and bound. Here, you may safely skip some subtrees since, depending on your particular optimization problem, you know in advance that no node within a certain subtree can yeld a better solution than the current one during the execution of your algorithm.