Split combinations: iterative algorithm O(N) = 2**N. based on binary represenation split

split_combination.py

def split_combination(s):
  "iterative algorythm O(N) = 2**N. based on binary represenation split"
  
  l = len(s)-1
  all_comb = []
  for i in range(2**l):
      splitmap = bin(i)[2:].rjust(l,'0')
      combination = []
      substr = s[0]
      for splitflag, char in zip(splitmap, s[1:]):
          if splitflag == '1':
              substr = substr + char
          else:
              combination.append(substr)
              substr = char
      combination.append(substr)
      all_comb.append(combination) # or better yield combination for generator
      # print('DEBUG:', combination)
      return all_comb
  
s = 'qwerty'
print(split_combination(s))
# [['q', 'w', 'e', 'r', 't', 'y'],
# ['q', 'w', 'e', 'r', 'ty'],
# ['q', 'w', 'e', 'rt', 'y'],
# ['q', 'w', 'e', 'rty'],
# ['q', 'w', 'er', 't', 'y'],
# ['q', 'w', 'er', 'ty'],
# ['q', 'w', 'ert', 'y'],
# ['q', 'w', 'erty'],
# ['q', 'we', 'r', 't', 'y'],
# ['q', 'we', 'r', 'ty'],
# ['q', 'we', 'rt', 'y'],
# ['q', 'we', 'rty'],
# ['q', 'wer', 't', 'y'],
# ['q', 'wer', 'ty'],
# ['q', 'wert', 'y'],
# ['q', 'werty'],
# ['qw', 'e', 'r', 't', 'y'],
# ['qw', 'e', 'r', 'ty'],
# ['qw', 'e', 'rt', 'y'],
# ['qw', 'e', 'rty'],
# ['qw', 'er', 't', 'y'],
# ['qw', 'er', 'ty'],
# ['qw', 'ert', 'y'],
# ['qw', 'erty'],
# ['qwe', 'r', 't', 'y'],
# ['qwe', 'r', 'ty'],
# ['qwe', 'rt', 'y'],
# ['qwe', 'rty'],
# ['qwer', 't', 'y'],
# ['qwer', 'ty'],
# ['qwert', 'y'],
# ['qwerty']]