#!/usr/bin/env python
# coding: utf-8

# # 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:
# 
# ```
# sky
# 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


# In[ ]: