Python: найти все возможные словосочетания с последовательностью символов (сегментация слов)

Я провожу несколько экспериментов по сегментации слов, например:

lst представляет собой последовательность символов, иoutput это все возможные слова.

lst = ['a', 'b', 'c', 'd']

def foo(lst):
    ...
    return output

output = [['a', 'b', 'c', 'd'],
          ['ab', 'c', 'd'],
          ['a', 'bc', 'd'],
          ['a', 'b', 'cd'],
          ['ab', 'cd'],
          ['abc', 'd'],
          ['a', 'bcd'],
          ['abcd']]

Я проверилcombinations а такжеpermutations вitertools библиотека,
а также попробовалкомбинаторика.
Однако, похоже, что я смотрю не с той стороны, потому что это не чистая перестановка и комбинации ...

Кажется, что я могу добиться этого, используя много циклов, но эффективность может быть низкой.

РЕДАКТИРОВАТЬ

Порядок слов важен, поэтому такие комбинации, как['ba', 'dc'] или же['cd', 'ab'] не действительны.

Порядок всегда должен бытьслева направо.

РЕДАКТИРОВАТЬ

Решение @ Stuart не работает в Python 2.7.6

РЕДАКТИРОВАТЬ

Решение @ Stuart работает в Python 2.7.6, см. Комментарии ниже.