In how many ways can you split a string into all possible substrings?

I recently chatted with a friend about the following question. Let's say that you have a string, say "sky". In how many ways can you split it into substrings. All possibilities are:

sk y
s ky
s k y

Intuitively, I suspected an answer similar to $ 2^{n} $, but I didn't sit down to figure out the exact answer.

So let's solve this problem. If we start with a string which's length is N then each split can be represented in a binary form of length N. For example:

sk y = 01 1

A 1 shows that we are ending a string with the character corresponding to this 1 and a 0 shows that we're continuing a string. If we have a 0 in the beginning, we're just continuing the empty string. So in our example, 01 corresonds to sk and the ending 1 corresponds to y. We have to notice that a valid split always ends with 1, because we're always ending at the end of the original word. Furthermore, all binary representations of the first N-1 characters corresponds to a possible split.

We can now see that the answer to the question is $ 2^{N-1} $.

Knowing this mapping between splits and binary numbers, we can even write some code that uses this property. It looks like this:

In [1]:
word = "rain"
N = len(word)

for b in range(2**(N-1)):
  split = '{0:03b}'.format(b)[::-1] + '1 '
  for i in range(len(word)):
    split += word[i]
    if b & (1 << i):
      split += ' '
  print split
0001 rain
1001 r ain
0101 ra in
1101 r a in
0011 rai n
1011 r ai n
0111 ra i n
1111 r a i n
In [ ]: