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.
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