Posted on by Kalkicode
Code Backtracking

# Possible ways to break a string using brackets

The problem at hand is about finding all possible ways to break a given string using brackets. The goal is to generate all possible combinations of substrings of the input string enclosed within brackets. For example, given the input string "123", the output should include "(1)(2)(3)", "(1)(23)", "(12)(3)", and "(123)".

## Problem Statement and Description

We are given a string, and our task is to generate all possible combinations of substrings from the given string using brackets. Each substring should be enclosed within brackets, and the order of the substrings should be maintained as they appear in the original string.

For instance, if the input string is "ABCD", the possible combinations of substrings using brackets are:

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

## Idea to Solve the Problem

To solve this problem, we can use a recursive approach. The idea is to start with an empty output string and iterate through the input string. At each iteration, we consider a substring that starts from the current position and extends to the end of the string. We recursively explore all possibilities by including the current substring within brackets and moving to the next position.

## Pseudocode

``````subString(text, start, last):
value = ""
for i from start to last:
append text[i] to value
return value

generate(text, output, start, last):
if start equals last:
print output
return
for i from start to last - 1:
generate(
text,
output + "(" + subString(text, start, i) + ")",
i + 1,
last
)``````

## Algorithm Explanation

1. `subString(text, start, last)` is a helper function that returns a substring of `text` starting from the `start` index and ending at the `last` index.

2. `generate(text, output, start, last)` is the main recursive function. It takes the input string `text`, the current output string `output`, the `start` index, and the `last` index as parameters.

3. If `start` is equal to `last`, it means we have processed all characters of the string, and we print the current output.

4. Otherwise, we iterate from `start` to `last - 1` (inclusive) using the index `i`. In each iteration, we generate a new output by enclosing the substring from `start` to `i` within brackets, and then recursively call `generate` with the new output and the next index (`i + 1`).

## Code Solution

``````/*
Java program for
Possible ways to break a string using brackets
*/
class Permutation
{
public String subString(String text, int start, int last)
{
String value = "";
for (int i = start; i <= last; ++i)
{
value = value + text.charAt(i);
}
return value;
}
public void generate(String text, String output, int start, int last)
{
if (start == last)
{
System.out.println(output);
return;
}
for (int i = start; i < last; ++i)
{
generate(text,
output + "(" + subString(text, start, (i)) + ")",
i + 1,
last);
}
}
public static void main(String[] args)
{
String text1 = "123456";
String text2 = "ABCD";
// Case 1
System.out.println("Given Text : " + text1);
// Case 2
System.out.println("\nGiven Text : " + text2);
}
}``````

#### Output

``````Given Text : 123456
(1)(2)(3)(4)(5)(6)
(1)(2)(3)(4)(56)
(1)(2)(3)(45)(6)
(1)(2)(3)(456)
(1)(2)(34)(5)(6)
(1)(2)(34)(56)
(1)(2)(345)(6)
(1)(2)(3456)
(1)(23)(4)(5)(6)
(1)(23)(4)(56)
(1)(23)(45)(6)
(1)(23)(456)
(1)(234)(5)(6)
(1)(234)(56)
(1)(2345)(6)
(1)(23456)
(12)(3)(4)(5)(6)
(12)(3)(4)(56)
(12)(3)(45)(6)
(12)(3)(456)
(12)(34)(5)(6)
(12)(34)(56)
(12)(345)(6)
(12)(3456)
(123)(4)(5)(6)
(123)(4)(56)
(123)(45)(6)
(123)(456)
(1234)(5)(6)
(1234)(56)
(12345)(6)
(123456)

Given Text : ABCD
(A)(B)(C)(D)
(A)(B)(CD)
(A)(BC)(D)
(A)(BCD)
(AB)(C)(D)
(AB)(CD)
(ABC)(D)
(ABCD)``````
``````// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
C++ program for
Possible ways to break a string using brackets
*/
class Permutation
{
public: string subString(string text, int start, int last)
{
string value = "";
for (int i = start; i <= last; ++i)
{
value = value  +  text[i];
}
return value;
}
void generate(string text, string output, int start, int last)
{
if (start == last)
{
cout << output << endl;
return;
}
for (int i = start; i < last; ++i)
{
this->generate(text,
output  +  "("
+  this->subString(text, start, (i))  +  ")",
i + 1, last);
}
}
};
int main()
{
string text1 = "123456";
string text2 = "ABCD";
// Case 1
cout << "Given Text : " << text1 << endl;
// Case 2
cout << "\nGiven Text : " << text2 << endl;
return 0;
}``````

#### Output

``````Given Text : 123456
(1)(2)(3)(4)(5)(6)
(1)(2)(3)(4)(56)
(1)(2)(3)(45)(6)
(1)(2)(3)(456)
(1)(2)(34)(5)(6)
(1)(2)(34)(56)
(1)(2)(345)(6)
(1)(2)(3456)
(1)(23)(4)(5)(6)
(1)(23)(4)(56)
(1)(23)(45)(6)
(1)(23)(456)
(1)(234)(5)(6)
(1)(234)(56)
(1)(2345)(6)
(1)(23456)
(12)(3)(4)(5)(6)
(12)(3)(4)(56)
(12)(3)(45)(6)
(12)(3)(456)
(12)(34)(5)(6)
(12)(34)(56)
(12)(345)(6)
(12)(3456)
(123)(4)(5)(6)
(123)(4)(56)
(123)(45)(6)
(123)(456)
(1234)(5)(6)
(1234)(56)
(12345)(6)
(123456)

Given Text : ABCD
(A)(B)(C)(D)
(A)(B)(CD)
(A)(BC)(D)
(A)(BCD)
(AB)(C)(D)
(AB)(CD)
(ABC)(D)
(ABCD)``````
``````// Include namespace system
using System;
/*
Csharp program for
Possible ways to break a string using brackets
*/
public class Permutation
{
public String subString(String text, int start, int last)
{
String value = "";
for (int i = start; i <= last; ++i)
{
value = value + text[i];
}
return value;
}
public void generate(String text, String output, int start, int last)
{
if (start == last)
{
Console.WriteLine(output);
return;
}
for (int i = start; i < last; ++i)
{
this.generate(text,
output + "(" + this.subString(text, start, (i)) + ")",
i + 1, last);
}
}
public static void Main(String[] args)
{
String text1 = "123456";
String text2 = "ABCD";
// Case 1
Console.WriteLine("Given Text : " + text1);
// Case 2
Console.WriteLine("\nGiven Text : " + text2);
}
}``````

#### Output

``````Given Text : 123456
(1)(2)(3)(4)(5)(6)
(1)(2)(3)(4)(56)
(1)(2)(3)(45)(6)
(1)(2)(3)(456)
(1)(2)(34)(5)(6)
(1)(2)(34)(56)
(1)(2)(345)(6)
(1)(2)(3456)
(1)(23)(4)(5)(6)
(1)(23)(4)(56)
(1)(23)(45)(6)
(1)(23)(456)
(1)(234)(5)(6)
(1)(234)(56)
(1)(2345)(6)
(1)(23456)
(12)(3)(4)(5)(6)
(12)(3)(4)(56)
(12)(3)(45)(6)
(12)(3)(456)
(12)(34)(5)(6)
(12)(34)(56)
(12)(345)(6)
(12)(3456)
(123)(4)(5)(6)
(123)(4)(56)
(123)(45)(6)
(123)(456)
(1234)(5)(6)
(1234)(56)
(12345)(6)
(123456)

Given Text : ABCD
(A)(B)(C)(D)
(A)(B)(CD)
(A)(BC)(D)
(A)(BCD)
(AB)(C)(D)
(AB)(CD)
(ABC)(D)
(ABCD)``````
``````package main
import "fmt"
/*
Go program for
Possible ways to break a string using brackets
*/

func subString(text string, start int, last int) string {
var value string = ""
for i := start ; i <= last ; i++ {
value = value + string(text[i])
}
return value
}
func generate(text string,
output string,
start int,
last int) {
if start == last {
fmt.Println(output)
return
}
for i := start ; i < last ; i++ {
generate(text,
output + "(" + subString(text, start, (i)) + ")",
i + 1, last)
}
}
func main() {

var text1 string = "123456"
var text2 string = "ABCD"
// Case 1
fmt.Println("Given Text : ", text1)
generate(text1, "", 0, len(text1))
// Case 2
fmt.Println("\nGiven Text : ", text2)
generate(text2, "", 0, len(text2))
}``````

#### Output

``````Given Text : 123456
(1)(2)(3)(4)(5)(6)
(1)(2)(3)(4)(56)
(1)(2)(3)(45)(6)
(1)(2)(3)(456)
(1)(2)(34)(5)(6)
(1)(2)(34)(56)
(1)(2)(345)(6)
(1)(2)(3456)
(1)(23)(4)(5)(6)
(1)(23)(4)(56)
(1)(23)(45)(6)
(1)(23)(456)
(1)(234)(5)(6)
(1)(234)(56)
(1)(2345)(6)
(1)(23456)
(12)(3)(4)(5)(6)
(12)(3)(4)(56)
(12)(3)(45)(6)
(12)(3)(456)
(12)(34)(5)(6)
(12)(34)(56)
(12)(345)(6)
(12)(3456)
(123)(4)(5)(6)
(123)(4)(56)
(123)(45)(6)
(123)(456)
(1234)(5)(6)
(1234)(56)
(12345)(6)
(123456)

Given Text : ABCD
(A)(B)(C)(D)
(A)(B)(CD)
(A)(BC)(D)
(A)(BCD)
(AB)(C)(D)
(AB)(CD)
(ABC)(D)
(ABCD)``````
``````<?php
/*
Php program for
Possible ways to break a string using brackets
*/
class Permutation
{
public	function subString(\$text, \$start, \$last)
{
\$value = "";
for (\$i = \$start; \$i <= \$last; ++\$i)
{
\$value = \$value.\$text[\$i];
}
return \$value;
}
public	function generate(\$text, \$output, \$start, \$last)
{
if (\$start == \$last)
{
echo(\$output.
"\n");
return;
}
for (\$i = \$start; \$i < \$last; ++\$i)
{
\$this->generate(\$text, \$output.
"(".\$this->subString(\$text, \$start, (\$i)).
")", \$i + 1, \$last);
}
}
}

function main()
{
\$text1 = "123456";
\$text2 = "ABCD";
// Case 1
echo("Given Text : ".\$text1.
"\n");
// Case 2
echo("\nGiven Text : ".\$text2.
"\n");
}
main();``````

#### Output

``````Given Text : 123456
(1)(2)(3)(4)(5)(6)
(1)(2)(3)(4)(56)
(1)(2)(3)(45)(6)
(1)(2)(3)(456)
(1)(2)(34)(5)(6)
(1)(2)(34)(56)
(1)(2)(345)(6)
(1)(2)(3456)
(1)(23)(4)(5)(6)
(1)(23)(4)(56)
(1)(23)(45)(6)
(1)(23)(456)
(1)(234)(5)(6)
(1)(234)(56)
(1)(2345)(6)
(1)(23456)
(12)(3)(4)(5)(6)
(12)(3)(4)(56)
(12)(3)(45)(6)
(12)(3)(456)
(12)(34)(5)(6)
(12)(34)(56)
(12)(345)(6)
(12)(3456)
(123)(4)(5)(6)
(123)(4)(56)
(123)(45)(6)
(123)(456)
(1234)(5)(6)
(1234)(56)
(12345)(6)
(123456)

Given Text : ABCD
(A)(B)(C)(D)
(A)(B)(CD)
(A)(BC)(D)
(A)(BCD)
(AB)(C)(D)
(AB)(CD)
(ABC)(D)
(ABCD)``````
``````/*
Node JS program for
Possible ways to break a string using brackets
*/
class Permutation
{
subString(text, start, last)
{
var value = "";
for (var i = start; i <= last; ++i)
{
value = value + text.charAt(i);
}
return value;
}
generate(text, output, start, last)
{
if (start == last)
{
console.log(output);
return;
}
for (var i = start; i < last; ++i)
{
this.generate(text,
output + "(" + this.subString(text, start, (i)) + ")",
i + 1, last);
}
}
}

function main()
{
var text1 = "123456";
var text2 = "ABCD";
// Case 1
console.log("Given Text : " + text1);
// Case 2
console.log("\nGiven Text : " + text2);
}
main();``````

#### Output

``````Given Text : 123456
(1)(2)(3)(4)(5)(6)
(1)(2)(3)(4)(56)
(1)(2)(3)(45)(6)
(1)(2)(3)(456)
(1)(2)(34)(5)(6)
(1)(2)(34)(56)
(1)(2)(345)(6)
(1)(2)(3456)
(1)(23)(4)(5)(6)
(1)(23)(4)(56)
(1)(23)(45)(6)
(1)(23)(456)
(1)(234)(5)(6)
(1)(234)(56)
(1)(2345)(6)
(1)(23456)
(12)(3)(4)(5)(6)
(12)(3)(4)(56)
(12)(3)(45)(6)
(12)(3)(456)
(12)(34)(5)(6)
(12)(34)(56)
(12)(345)(6)
(12)(3456)
(123)(4)(5)(6)
(123)(4)(56)
(123)(45)(6)
(123)(456)
(1234)(5)(6)
(1234)(56)
(12345)(6)
(123456)

Given Text : ABCD
(A)(B)(C)(D)
(A)(B)(CD)
(A)(BC)(D)
(A)(BCD)
(AB)(C)(D)
(AB)(CD)
(ABC)(D)
(ABCD)``````
``````#    Python 3 program for
#    Possible ways to break a string using brackets
class Permutation :
def subString(self, text, start, last) :
value = ""
i = start
while (i <= last) :
value = value + str(text[i])
i += 1

return value

def generate(self, text, output, start, last) :
if (start == last) :
print(output)
return

i = start
while (i < last) :
self.generate(text,
output + "(" + self.subString(text, start, (i)) + ")",
i + 1, last)
i += 1

def main() :
text1 = "123456"
text2 = "ABCD"
#  Case 1
print("Given Text : ", text1)
#  Case 2
print("\nGiven Text : ", text2)

if __name__ == "__main__": main()``````

#### Output

``````Given Text :  123456
(1)(2)(3)(4)(5)(6)
(1)(2)(3)(4)(56)
(1)(2)(3)(45)(6)
(1)(2)(3)(456)
(1)(2)(34)(5)(6)
(1)(2)(34)(56)
(1)(2)(345)(6)
(1)(2)(3456)
(1)(23)(4)(5)(6)
(1)(23)(4)(56)
(1)(23)(45)(6)
(1)(23)(456)
(1)(234)(5)(6)
(1)(234)(56)
(1)(2345)(6)
(1)(23456)
(12)(3)(4)(5)(6)
(12)(3)(4)(56)
(12)(3)(45)(6)
(12)(3)(456)
(12)(34)(5)(6)
(12)(34)(56)
(12)(345)(6)
(12)(3456)
(123)(4)(5)(6)
(123)(4)(56)
(123)(45)(6)
(123)(456)
(1234)(5)(6)
(1234)(56)
(12345)(6)
(123456)

Given Text :  ABCD
(A)(B)(C)(D)
(A)(B)(CD)
(A)(BC)(D)
(A)(BCD)
(AB)(C)(D)
(AB)(CD)
(ABC)(D)
(ABCD)``````
``````#    Ruby program for
#    Possible ways to break a string using brackets
class Permutation
def subString(text, start, last)
value = ""
i = start
while (i <= last)
value = value + text[i].to_s
i += 1
end

return value
end

def generate(text, output, start, last)
if (start == last)
print(output, "\n")
return
end

i = start
while (i < last)
self.generate(text,
output + "(" + self.subString(text, start, (i)) + ")",
i + 1, last)
i += 1
end

end

end

def main()
text1 = "123456"
text2 = "ABCD"
#  Case 1
print("Given Text : ", text1, "\n")
#  Case 2
print("\nGiven Text : ", text2, "\n")
end

main()``````

#### Output

``````Given Text : 123456
(1)(2)(3)(4)(5)(6)
(1)(2)(3)(4)(56)
(1)(2)(3)(45)(6)
(1)(2)(3)(456)
(1)(2)(34)(5)(6)
(1)(2)(34)(56)
(1)(2)(345)(6)
(1)(2)(3456)
(1)(23)(4)(5)(6)
(1)(23)(4)(56)
(1)(23)(45)(6)
(1)(23)(456)
(1)(234)(5)(6)
(1)(234)(56)
(1)(2345)(6)
(1)(23456)
(12)(3)(4)(5)(6)
(12)(3)(4)(56)
(12)(3)(45)(6)
(12)(3)(456)
(12)(34)(5)(6)
(12)(34)(56)
(12)(345)(6)
(12)(3456)
(123)(4)(5)(6)
(123)(4)(56)
(123)(45)(6)
(123)(456)
(1234)(5)(6)
(1234)(56)
(12345)(6)
(123456)

Given Text : ABCD
(A)(B)(C)(D)
(A)(B)(CD)
(A)(BC)(D)
(A)(BCD)
(AB)(C)(D)
(AB)(CD)
(ABC)(D)
(ABCD)
``````
``````import scala.collection.mutable._;
/*
Scala program for
Possible ways to break a string using brackets
*/
class Permutation()
{
def subString(text: String,
start: Int,
last: Int): String = {
var value: String = "";
var i: Int = start;
while (i <= last)
{
value = value + text.charAt(i).toString();
i += 1;
}
return value;
}
def generate(
text: String,
output: String,
start: Int,
last: Int): Unit = {
if (start == last)
{
println(output);
return;
}
var i: Int = start;
while (i < last)
{
generate(text,
output + "(" + subString(text, start, (i)) + ")",
i + 1, last);
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Permutation = new Permutation();
var text1: String = "123456";
var text2: String = "ABCD";
// Case 1
println("Given Text : " + text1);
// Case 2
println("\nGiven Text : " + text2);
}
}``````

#### Output

``````Given Text : 123456
(1)(2)(3)(4)(5)(6)
(1)(2)(3)(4)(56)
(1)(2)(3)(45)(6)
(1)(2)(3)(456)
(1)(2)(34)(5)(6)
(1)(2)(34)(56)
(1)(2)(345)(6)
(1)(2)(3456)
(1)(23)(4)(5)(6)
(1)(23)(4)(56)
(1)(23)(45)(6)
(1)(23)(456)
(1)(234)(5)(6)
(1)(234)(56)
(1)(2345)(6)
(1)(23456)
(12)(3)(4)(5)(6)
(12)(3)(4)(56)
(12)(3)(45)(6)
(12)(3)(456)
(12)(34)(5)(6)
(12)(34)(56)
(12)(345)(6)
(12)(3456)
(123)(4)(5)(6)
(123)(4)(56)
(123)(45)(6)
(123)(456)
(1234)(5)(6)
(1234)(56)
(12345)(6)
(123456)

Given Text : ABCD
(A)(B)(C)(D)
(A)(B)(CD)
(A)(BC)(D)
(A)(BCD)
(AB)(C)(D)
(AB)(CD)
(ABC)(D)
(ABCD)``````
``````import Foundation;
/*
Swift 4 program for
Possible ways to break a string using brackets
*/
class Permutation
{
func subString(_ text: [Character],
_ start: Int,
_ last: Int) -> String
{
var value: String = "";
var i: Int = start;
while (i <= last)
{
value = value + String(text[i]);
i += 1;
}
return value;
}
func generate(_ text: String,
_ output: String,
_ start: Int,
_ last: Int)
{
if (start == last)
{
print(output);
return;
}
var i: Int = start;
let arr = Array(text);
while (i < last)
{
self.generate(text,
output + "(" + self.subString(arr, start, (i)) + ")",
i + 1, last);
i += 1;
}
}
}
func main()
{
let text1: String = "123456";
let text2: String = "ABCD";
// Case 1
print("Given Text : ", text1);
// Case 2
print("\nGiven Text : ", text2);
}
main();``````

#### Output

``````Given Text :  123456
(1)(2)(3)(4)(5)(6)
(1)(2)(3)(4)(56)
(1)(2)(3)(45)(6)
(1)(2)(3)(456)
(1)(2)(34)(5)(6)
(1)(2)(34)(56)
(1)(2)(345)(6)
(1)(2)(3456)
(1)(23)(4)(5)(6)
(1)(23)(4)(56)
(1)(23)(45)(6)
(1)(23)(456)
(1)(234)(5)(6)
(1)(234)(56)
(1)(2345)(6)
(1)(23456)
(12)(3)(4)(5)(6)
(12)(3)(4)(56)
(12)(3)(45)(6)
(12)(3)(456)
(12)(34)(5)(6)
(12)(34)(56)
(12)(345)(6)
(12)(3456)
(123)(4)(5)(6)
(123)(4)(56)
(123)(45)(6)
(123)(456)
(1234)(5)(6)
(1234)(56)
(12345)(6)
(123456)

Given Text :  ABCD
(A)(B)(C)(D)
(A)(B)(CD)
(A)(BC)(D)
(A)(BCD)
(AB)(C)(D)
(AB)(CD)
(ABC)(D)
(ABCD)``````
``````/*
Kotlin program for
Possible ways to break a string using brackets
*/
class Permutation
{
fun subString(text: String,
start: Int,
last: Int): String
{
var value: String = "";
var i: Int = start;
while (i <= last)
{
value = value + text.get(i).toString();
i += 1;
}
return value;
}
fun generate(text: String,
output: String,
start: Int,
last: Int): Unit
{
if (start == last)
{
println(output);
return;
}
var i: Int = start;
while (i < last)
{
this.generate(text,
output + "(" + this.subString(text, start, (i)) + ")",
i + 1, last);
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val text1: String = "123456";
val text2: String = "ABCD";
// Case 1
println("Given Text : " + text1);
// Case 2
println("\nGiven Text : " + text2);
}``````

#### Output

``````Given Text : 123456
(1)(2)(3)(4)(5)(6)
(1)(2)(3)(4)(56)
(1)(2)(3)(45)(6)
(1)(2)(3)(456)
(1)(2)(34)(5)(6)
(1)(2)(34)(56)
(1)(2)(345)(6)
(1)(2)(3456)
(1)(23)(4)(5)(6)
(1)(23)(4)(56)
(1)(23)(45)(6)
(1)(23)(456)
(1)(234)(5)(6)
(1)(234)(56)
(1)(2345)(6)
(1)(23456)
(12)(3)(4)(5)(6)
(12)(3)(4)(56)
(12)(3)(45)(6)
(12)(3)(456)
(12)(34)(5)(6)
(12)(34)(56)
(12)(345)(6)
(12)(3456)
(123)(4)(5)(6)
(123)(4)(56)
(123)(45)(6)
(123)(456)
(1234)(5)(6)
(1234)(56)
(12345)(6)
(123456)

Given Text : ABCD
(A)(B)(C)(D)
(A)(B)(CD)
(A)(BC)(D)
(A)(BCD)
(AB)(C)(D)
(AB)(CD)
(ABC)(D)
(ABCD)``````

## Time Complexity

The time complexity of this algorithm depends on the number of recursive calls made. In the worst case, each character of the string is considered at least once in a recursive call. Since we are generating all possible combinations, the total number of outputs will be exponential in the length of the input string. Therefore, the time complexity is O(2^n), where n is the length of the input string.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post