Unfortunatedly the runtime efficiency of anything that uses this is O(n!) which is even worse than exponential. Oh my...

Oh, you want an efficient algorithm. Why didn't you say so? There's a linear-time bottom-up algorithm in Aho, Hopcroft, Ullman's The Design and Analysis of Algorithms. Online I've found it at http://cgm.cs.mcgill.ca/~msuder/courses/250/assignments/5/5.pdf