Разбить строку на слова

Я ищу наиболее эффективный алгоритм для формирования всех возможных комбинаций слов из строки. Например:

Input String: forevercarrot

Output:

forever carrot
forever car rot
for ever carrot
for ever car rot

(Все слова должны быть из словаря.)

Я могу думать о подходе грубой силы. (найти все возможные подстроки и сопоставить), но что было бы лучше?