# 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 recurse for remaining substring [i+1, n-1]. If every substring of original string is processed, we print the output string.

Below is C++ and Java implementation of the idea –

Output:

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

## Java

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.

(1 votes, average: 5.00 out of 5)

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 🙂

Subscribe
Notify of
Guest

can you explain how the complexity came out to be 2^n-1? I have below implementation in C.

printsubstring(str, start, n)
{
for (k = 1; k <=size && (start + k) < n; k++)
{
print_string(str, start, start + k); // prints with paranthesis
printsubstring(str, start + k, n);
}
}