generating all the covering substrings of a string

Question

How do you the following: given a string, generate all the possible ways to parse that string into substrings (time is important, space dont' care). For example, given the string ABCD, I need to generate:

ABCD

A BCD

A BC D

A B CD

AB CD

AB C D

ABC D

A B C D

Probably a recursive solution, but I can't quite get it to work.

Answer 1

Python:

def splitstring(s):
  result = [s]
  for i in range(1, len(s)):
    result.extend('%s %s' % (s[:i], x) for x in splitstring(s[i:]))
  return result