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))
3. (Square) You're given an array L which represents the sizes of n planks. You have to answer if there's any way to form a square using the planks without breaking them of overlapping them. (complexity O(4^n/2))
4. (15 puzzle) Solve 15 puzzle in at most 40 moves.

5. (pancake puzzle) sort pancakes in optimal number of moves.

Try the to solve these problems in the comment section.
http://www.cs.cornell.edu/~wdtseng/icpc/notes/bt3.pdf