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)
	{
		Permutation task = new Permutation();
		String text1 = "123456";
		String text2 = "ABCD";
		// Case 1  
		System.out.println("Given Text : " + text1);
		task.generate(text1, "", 0, text1.length());
		// Case 2  
		System.out.println("\nGiven Text : " + text2);
		task.generate(text2, "", 0, text2.length());
	}
}

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()
{
	Permutation *task = new Permutation();
	string text1 = "123456";
	string text2 = "ABCD";
	// Case 1  
	cout << "Given Text : " << text1 << endl;
	task->generate(text1, "", 0, text1.length());
	// Case 2  
	cout << "\nGiven Text : " << text2 << endl;
	task->generate(text2, "", 0, text2.length());
	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)
	{
		Permutation task = new Permutation();
		String text1 = "123456";
		String text2 = "ABCD";
		// Case 1  
		Console.WriteLine("Given Text : " + text1);
		task.generate(text1, "", 0, text1.Length);
		// Case 2  
		Console.WriteLine("\nGiven Text : " + text2);
		task.generate(text2, "", 0, text2.Length);
	}
}

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()
{
	$task = new Permutation();
	$text1 = "123456";
	$text2 = "ABCD";
	// Case 1  
	echo("Given Text : ".$text1.
		"\n");
	$task->generate($text1, "", 0, strlen($text1));
	// Case 2  
	echo("\nGiven Text : ".$text2.
		"\n");
	$task->generate($text2, "", 0, strlen($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)
/*
    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 task = new Permutation();
	var text1 = "123456";
	var text2 = "ABCD";
	// Case 1  
	console.log("Given Text : " + text1);
	task.generate(text1, "", 0, text1.length);
	// Case 2  
	console.log("\nGiven Text : " + text2);
	task.generate(text2, "", 0, text2.length);
}
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() :
	task = Permutation()
	text1 = "123456"
	text2 = "ABCD"
	#  Case 1  
	print("Given Text : ", text1)
	task.generate(text1, "", 0, len(text1))
	#  Case 2  
	print("\nGiven Text : ", text2)
	task.generate(text2, "", 0, len(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() 
	task = Permutation.new()
	text1 = "123456"
	text2 = "ABCD"
	#  Case 1  
	print("Given Text : ", text1, "\n")
	task.generate(text1, "", 0, text1.length)
	#  Case 2  
	print("\nGiven Text : ", text2, "\n")
	task.generate(text2, "", 0, text2.length)
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);
		task.generate(text1, "", 0, text1.length());
		// Case 2  
		println("\nGiven Text : " + text2);
		task.generate(text2, "", 0, text2.length());
	}
}

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 task: Permutation = Permutation();
	let text1: String = "123456";
	let text2: String = "ABCD";
	// Case 1  
	print("Given Text : ", text1);
	task.generate(text1, "", 0, text1.count);
	// Case 2  
	print("\nGiven Text : ", text2);
	task.generate(text2, "", 0, text2.count);
}
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 task: Permutation = Permutation();
	val text1: String = "123456";
	val text2: String = "ABCD";
	// Case 1  
	println("Given Text : " + text1);
	task.generate(text1, "", 0, text1.length);
	// Case 2  
	println("\nGiven Text : " + text2);
	task.generate(text2, "", 0, text2.length);
}

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.

New Comment





Categories
Relative Post