Break a string into all possible combinations of non-overlapping substrings

Given a string, break it into all possible combinations of non-overlapping substrings enclosed within curly brackets.


 

For example,


Input: ABC

Output:

{ABC}
{AB}{C}
{A}{BC}
{A}{B}{C}

 
Input: ABCD

Output:

{ABCD}
{ABC}{D}
{AB}{CD}
{AB}{C}{D}
{A}{BCD}
{A}{BC}{D}
{A}{B}{CD}
{A}{B}{C}{D}

 
We can use recursion to solve this problem. The idea is to maintain two parameters – index of the next character to be processed and the result string so far. We start from index of next character to be processed, append substring formed by unprocessed string to the result string and recurse on remaining string until we process the whole string.

The diagram below represents recursion tree for string abc. In each tree node, the processed part is shown by the green color and the unprocessed string is shown by the red color.

non-overlapping substrings

 
Below is C++ and Java implementation based on above idea –

C++

Download   Run Code

Java

Download   Run Code

Output:

{ABCD}
{ABC}{D}
{AB}{CD}
{AB}{C}{D}
{A}{BCD}
{A}{BC}{D}
{A}{B}{CD}
{A}{B}{C}{D}

 
Author: Aditya Goel

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
Notify of