# 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.