Hey guys,

Today I had an interview with sharechat for SDE-2 role, the interviewer asked this question, I tried recursive and iterative but couldn't solve. I am weak in solving combinations related problems. I tried iterative with O(n^3) approach but did not solve completely. So, bombed the interivew, it's gone.

Question

Given a string with n characters. Find all the possible combination of making a sentence from it in the same order. A sentence is a statement generated by using 1 or more words.
Example: uvqx
possible strings:
u v q x
uv qx
uv q x
uvqx
u vq x
u vqx
u v qx
uvq x