For the record, this is an easy application of itertools.combinations:

>>> def segment(s, m):
...     for c in itertools.combinations(range(1, len(s)), m-1):
...         yield tuple(s[i:j] for i, j in zip((0,)+c, c+(len(s),)))
... 
>>> list(segment("12345", m=3))
[('1', '2', '345'), ('1', '23', '45'), ('1', '234', '5'), ('12', '3', '45'), ('12', '34', '5'), ('123', '4', '5')]