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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂


Leave a Reply

avatar
  Subscribe  
Notify of