h1. Meet in the middle

Meet in the middle (sometimes called split and merge) is a clever approach which tries to trade off space for time.
Let’s discuss a few applications.

Now the application of meet in the middle becomes obvious. We can brute force through the numbers on each side of the equality and find a match.
This algorithm takes O(sqrt(n)) space and O(sqrt(n)) time.

h2. Minimal vertex cover
 
bq. Given a graph of n nodes (n <= 30), find out a set with the smallest number of vertices such that each edge in the graph has at least one node inside the set.
 
As before we split the nodes in half. We’ll brute force the set of vertices that are in the first half of the nodes and in a minimum vertex cover. For edges (f, s) where node f is in the first half but not in our picked set and s in the second half we have to use s to cover the edge. Now we’re left with edges that have both end nodes in the second half. We compute the minimum edge cover for each induced subgraph. O(3^n).
 

h2. Additional problems

1. (Equal partition) Given a set A of 40 real numbers, find out if there is any way to split A in two sets such that the sums of their elements are equal.
2. (Maximum independent set) Given a graph of 30 vertices. Find a set that contains the most number of nodes such that no two nodes in the set are connected by an edge.

1. (Equal partition) Given a set A of 40 real numbers, find out if there is any way to split A in two sets such that the sums of their elements are equal. (O(2^n))
2. (minimal vertex cover) Given a graph of n nodes (n <= 30), find out a set with the smallest number of vertices such that each edge in the  graph has at least one node inside the set. (O(3^n/2))

Try the to solve these two problems in the comment section.