Find all combinations of non-overlapping substrings of a string

Given a string, find all combinations of non-overlapping substrings of it. The solution should use parenthesis to split the string into non-overlapping substrings.

 

For example,


Input:  ABC
Output:

(A) (B) (C)
(A) (BC)
(AB) (C)
(ABC)
 

Input:  ABCD
Output:

(A) (B) (C) (D)
(A) (B) (CD)
(A) (BC) (D)
(A) (BCD)
(AB) (C) (D)
(AB) (CD)
(ABC) (D)
(ABCD)

 


 

The idea is to use recursion to solve this problem. For a given string of length n, we consider every prefix [0, i] of it one by one. We append the prefix to the output string by enclosing it within the parenthesis and recuse for remaining substring [i+1, n-1]. If every substring of original string is processed, we print the output string.

In solution below, we use a vector to store non-overlapping substrings.

 
C++ implementation –
 

Download   Run Code

Output:

(A) (B) (C) (D)
(A) (B) (CD)
(A) (BC) (D)
(A) (BCD)
(AB) (C) (D)
(AB) (CD)
(ABC) (D)
(ABCD)

The time complexity of above solution is exponential as there are exactly 2n-1 combinations. Here, n is length of the input string.
 

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 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz