Print all possible ways to break a string in bracket form

For the give input string, find all possible ways to break the given string in bracket form. Enclose all substrings within brackets ().

Examples

Input string : abcd

Output : (a)(b)(c)(d)
        (a)(b)(cd)
        (a)(bc)(d)
        (ab)(c)(d)
        (ab)(cd)
        (a)(bcd)
        (abc)(d)
        (abcd)   

Time complexity: O(n)

Algorithm

Here we use recursion, We maintain two parameters index of next character to be processed and output string so far.

1. We start from index of next character to be processed.

2. Append substring formed by unprocessed string to the output string and recur on remaining until we process the entire string.

3. We use substr(pos, n) to form the output string, this returns the substring of length n that starts at position pos if the current string.

C++ Program

#include <bits/stdc++.h>

using namespace std;
 
void PrintCombinations(string str, int index, string output)
{
    if (index == str.length())
    {
        cout<<output<<endl;
    }
    //Recursion on remaining part of string
    for (int i = index; i < str.length(); i ++)
    {
        PrintCombinations(str, i + 1, output +"(" + str.substr(index, i+1-index) + ")" );
    }
}
 
//Main function
int main()
{
    string input_string = "abcd";
    PrintCombinations(input_string, 0, "");
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top