'Finding all combinations of well-formed brackets
This came up while talking to a friend and I thought I'd ask here since it's an interesting problem and would like to see other people's solutions.
The task is to write a function Brackets(int n) that prints all combinations of well-formed brackets from 1...n. For Brackets(3) the output would be
()
(()) ()()
((())) (()()) (())() ()(()) ()()()
Solution 1:[1]
Python version of the first voted answer.
def foo(output, open, close, pairs):
if open == pairs and close == pairs:
print output
else:
if open<pairs:
foo(output+'(', open+1, close, pairs)
if close<open:
foo(output+')', open, close+1, pairs)
foo('', 0, 0, 3)
Solution 2:[2]
The number of possible combinations is the Catalan number of N pairs C(n).
This problem was discussed on the joelonsoftware.com forums pretty exentsively including iterative, recursive and iterative/bitshifting solutions. Some pretty cool stuff there.
Here is a quick recursive solution suggested on the forums in C#:
C#
public void Brackets(int pairs) {
if (pairs > 1) Brackets(pairs - 1);
char[] output = new char[2 * pairs];
output[0] = '(';
output[1] = ')';
foo(output, 1, pairs - 1, pairs, pairs);
Console.writeLine();
}
public void foo(char[] output, int index, int open, int close,
int pairs) {
int i;
if (index == 2 * pairs) {
for (i = 0; i < 2 * pairs; i++)
Console.write(output[i]);
Console.write('\n');
return;
}
if (open != 0) {
output[index] = '(';
foo(output, index + 1, open - 1, close, pairs);
}
if ((close != 0) && (pairs - close + 1 <= pairs - open)) {
output[index] = ')';
foo(output, index + 1, open, close - 1, pairs);
}
return;
}
Brackets(3);
Output:
()
(()) ()()
((())) (()()) (())() ()(()) ()()()
Solution 3:[3]
F#:
Here is a solution that, unlike my previous solution, I believe may be correct. Also, it is more efficient.
#light
let brackets2 n =
let result = new System.Collections.Generic.List<_>()
let a = Array.create (n*2) '_'
let rec helper l r diff i =
if l=0 && r=0 then
result.Add(new string(a))
else
if l > 0 then
a.[i] <- '('
helper (l-1) r (diff+1) (i+1)
if diff > 0 then
a.[i] <- ')'
helper l (r-1) (diff-1) (i+1)
helper n n 0 0
result
Example:
(brackets2 4) |> Seq.iter (printfn "%s")
(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)
Solution 4:[4]
Here's another F# solution, favoring elegance over efficiency, although memoization would probably lead to a relatively well performing variant.
let rec parens = function
| 0 -> [""]
| n -> [for k in 0 .. n-1 do
for p1 in parens k do
for p2 in parens (n-k-1) ->
sprintf "(%s)%s" p1 p2]
Again, this only yields a list of those strings with exactly n pairs of parens (rather than at most n), but it's easy to wrap it.
Solution 5:[5]
F#:
UPDATE: this answer is wrong. My N=4 misses, for example "(())(())". (Do you see why?) I will post a correct (and more efficient) algorithm shortly.
(Shame on all you up-voters, for not catching me! :) )
Inefficient, but short and simple. (Note that it only prints the 'nth' line; call in a loop from 1..n to get the output asked for by the question.)
#light
let rec brackets n =
if n = 1 then
["()"]
else
[for s in brackets (n-1) do
yield "()" ^ s
yield "(" ^ s ^ ")"
yield s ^ "()"]
Example:
Set.of_list (brackets 4) |> Set.iter (printfn "%s")
(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)
Solution 6:[6]
Simple solution in C++:
#include <iostream>
#include <string>
void brackets(string output, int open, int close, int pairs)
{
if(open == pairs && close == pairs)
cout << output << endl;
else
{
if(open<pairs)
brackets(output+"(",open+1,close,pairs);
if(close<open)
brackets(output+")",open,close+1,pairs);
}
}
int main()
{
for(int i=1;i<=3;i++)
{
cout << "Combination for i = " << i << endl;
brackets("",0,0,i);
}
}
Output:
Combination for i = 1
()
Combination for i = 2
(())
()()
Combination for i = 3
((()))
(()())
(())()
()(())
()()()
Solution 7:[7]
Damn - everyone beat me to it, but I have a nice working example :)
http://www.fiveminuteargument.com/so-727707
The key is identifying the rules, which are actually quite simple:
- Build the string char-by-char
- At a given point in the string
- if brackets in string so far balance (includes empty str), add an open bracket and recurse
- if all open brackets have been used, add a close bracket and recurse
- otherwise, recurse twice, once for each type of bracket
- Stop when you get to the end :-)
Solution 8:[8]
Common Lisp:
This doesn't print them, but does produce a list of lists of all the possible structures. My method is a bit different from the others'. It restructures the solutions to brackets(n - 1) such that they become brackets(n). My solution isn't tail recursive, but it could be made so with a little work.
Code
(defun brackets (n)
(if (= 1 n)
'((()))
(loop for el in (brackets (1- n))
when (cdr el)
collect (cons (list (car el)) (cdr el))
collect (list el)
collect (cons '() el))))
Solution 9:[9]
Here is a solution in C++. The main idea that I use is that I take the output from the previous i (where i is the number of bracket pairs), and feed that as input to the next i. Then, for each string in the input, we put a bracket pair at each location in the string. New strings are added to a set in order to eliminate duplicates.
#include <iostream>
#include <set>
using namespace std;
void brackets( int n );
void brackets_aux( int x, const set<string>& input_set, set<string>& output_set );
int main() {
int n;
cout << "Enter n: ";
cin >> n;
brackets(n);
return 0;
}
void brackets( int n ) {
set<string>* set1 = new set<string>;
set<string>* set2;
for( int i = 1; i <= n; i++ ) {
set2 = new set<string>;
brackets_aux( i, *set1, *set2 );
delete set1;
set1 = set2;
}
}
void brackets_aux( int x, const set<string>& input_set, set<string>& output_set ) {
// Build set of bracket strings to print
if( x == 1 ) {
output_set.insert( "()" );
}
else {
// For each input string, generate the output strings when inserting a bracket pair
for( set<string>::iterator s = input_set.begin(); s != input_set.end(); s++ ) {
// For each location in the string, insert bracket pair before location if valid
for( unsigned int i = 0; i < s->size(); i++ ) {
string s2 = *s;
s2.insert( i, "()" );
output_set.insert( s2 );
}
output_set.insert( *s + "()" );
}
}
// Print them
for( set<string>::iterator i = output_set.begin(); i != output_set.end(); i++ ) {
cout << *i << " ";
}
cout << endl;
}
Solution 10:[10]
A simple F#/OCaml solution :
let total_bracket n =
let rec aux acc = function
| 0, 0 -> print_string (acc ^ "\n")
| 0, n -> aux (acc ^ ")") (0, n-1)
| n, 0 -> aux (acc ^ "(") (n-1, 1)
| n, c ->
aux (acc ^ "(") (n-1, c+1);
aux (acc ^ ")") (n, c-1)
in
aux "" (n, 0)
Solution 11:[11]
Provider C# version based on recursive backtracking algorithm, hope it's helpful.
public List<String> generateParenthesis(int n) {
List<String> result = new LinkedList<String>();
Generate("", 0, 0, n, result);
return result;
}
private void Generate(String s, int l, int r, int n, List<String> result){
if(l == n && r == n){
result.add(s);
return;
}
if(l<n){
Generate(s+"(", l+1, r, n, result);
}
if(r < l)
Generate(s+")", l , r+1, n, result);
}}
Solution 12:[12]
def @memo brackets ( n )
=> [] if n == 0 else around( n ) ++ pre( n ) ++ post( n ) ++ [ "()" * n) ]
def @memo pre ( n )
=> map ( ( s ) => "()" ++ s, pre ( n - 1 ) ++ around ( n - 1 ) ) if n > 2 else []
def @memo post ( n )
=> map ( ( s ) => s ++ "()", post ( n - 1 ) ++ around ( n - 1 ) ) if n > 2 else []
def @memo around ( n )
=> map ( ( s ) => "(" ++ s ++ ")", brackets( n - 1 ) )
(kin, which is something like an actor model based linear python with traits. I haven't got round to implementing @memo but the above works without that optimisation)
Solution 13:[13]
Haskell:
I tried to come up with an elegant list monad-y way to this:
import Control.Applicative
brackets :: Int -> [String]
brackets n = f 0 0 where
f pos depth =
if pos < 2*n
then open <|> close
else stop where
-- Add an open bracket if we can
open =
if depth < 2*n - pos
then ('(' :) <$> f (pos+1) (depth+1)
else empty
-- Add a closing bracket if we can
close =
if depth > 0
then (')' :) <$> f (pos+1) (depth-1)
else empty
-- Stop adding text. We have 2*n characters now.
stop = pure ""
main = readLn >>= putStr . unlines . brackets
Solution 14:[14]
why cant this is as simple as this, this idea is quite simple
brackets(n) --> '()' + brackets(n-1) 0 '(' + brackets(n-1) + ')' 0 brackets(n-1) + '()'
where 0 is the concatenation operation above
public static Set<String> brackets(int n) {
if(n == 1){
Set<String> s = new HashSet<String>();
s.add("()");
return s;
}else{
Set<String> s1 = new HashSet<String>();
Set<String> s2 = brackets(n - 1);
for(Iterator<String> it = s2.iterator(); it.hasNext();){
String s = it.next();
s1.add("()" + s);
s1.add("(" + s + ")");
s1.add(s + "()");
}
s2.clear();
s2 = null;
return s1;
}
}
Solution 15:[15]
Groovy version based on markt's elegant c# solution above. Dynamically checking open and close (information was repeated in output and args) as well as removing a couple of extraneous logic checks.
3.times{
println bracks(it + 1)
}
def bracks(pairs, output=""){
def open = output.count('(')
def close = output.count(')')
if (close == pairs) {
print "$output "
}
else {
if (open < pairs) bracks(pairs, "$output(")
if (close < open) bracks(pairs, "$output)")
}
""
}
Solution 16:[16]
Not the most elegant solution, but this was how I did it in C++ (Visual Studio 2008). Leveraging the STL set to eliminate duplicates, I just naively insert new () pairs into each string index in every string from the previous generation, then recurse.
#include "stdafx.h"
#include <iostream>
#include <string>
#include <set>
using namespace System;
using namespace std;
typedef set<string> StrSet;
void ExpandSet( StrSet &Results, int Curr, int Max )
{
if (Curr < Max)
{
StrSet NewResults;
for (StrSet::iterator it = Results.begin(); it != Results.end(); ++it)
{
for (unsigned int stri=0; stri < (*it).length(); stri++)
{
string NewStr( *it );
NewResults.insert( NewStr.insert( stri, string("()") ) );
}
}
ExpandSet( NewResults, Curr+1, Max );
Results = NewResults;
}
}
int main(array<System::String ^> ^args)
{
int ParenCount = 0;
cout << "Enter the parens to balance:" << endl;
cin >> ParenCount;
StrSet Results;
Results.insert( string("()") );
ExpandSet(Results, 1, ParenCount);
cout << Results.size() << ": Total # of results for " << ParenCount << " parens:" << endl;
for (StrSet::iterator it = Results.begin(); it != Results.end(); ++it)
{
cout << *it << endl;
}
return 0;
}
Solution 17:[17]
//C program to print all possible n pairs of balanced parentheses
#include<stdio.h>
void fn(int p,int n,int o,int c);
void main()
{
int n;
printf("\nEnter n:");
scanf("%d",&n);
if(n>0)
fn(0,n,0,0);
}
void fn(int p,int n,into,int c)
{
static char str[100];
if(c==n)
{
printf("%s\n",str);
return;
}
else
{
if(o>c)
{
str[p]='}';
fn(p+1,n,o,c+1);
}
if(o<n)
{
str[p]='{';
fn(p+1,n;o+1,c);
}
}
}
Solution 18:[18]
ruby version:
def foo output, open, close, pairs
if open == pairs and close == pairs
p output
else
foo(output + '(', open+1, close, pairs) if open < pairs
foo(output + ')', open, close+1, pairs) if close < open
end
end
foo('', 0, 0, 3)
Solution 19:[19]
validParentheses: function validParentheses(n) {
if(n === 1) {
return ['()'];
}
var prevParentheses = validParentheses(n-1);
var list = {};
prevParentheses.forEach(function(item) {
list['(' + item + ')'] = null;
list['()' + item] = null;
list[item + '()'] = null;
});
return Object.keys(list);
}
Solution 20:[20]
public static void printAllValidBracePermutations(int size) {
printAllValidBracePermutations_internal("", 0, 2 * size);
}
private static void printAllValidBracePermutations_internal(String str, int bal, int len) {
if (len == 0) System.out.println(str);
else if (len > 0) {
if (bal <= len / 2) printAllValidBracePermutations_internal(str + "{", bal + 1, len - 1);
if (bal > 0) printAllValidBracePermutations_internal(str + "}", bal - 1, len - 1);
}
}
Solution 21:[21]
Another inefficient but elegant answer =>
public static Set<String> permuteParenthesis1(int num)
{
Set<String> result=new HashSet<String>();
if(num==0)//base case
{
result.add("");
return result;
}
else
{
Set<String> temp=permuteParenthesis1(num-1); // storing result from previous result.
for(String str : temp)
{
for(int i=0;i<str.length();i++)
{
if(str.charAt(i)=='(')
{
result.add(insertParen(str, i)); // addinng `()` after every left parenthesis.
}
}
result.add("()"+str); // adding "()" to the beginning.
}
}
return result;
}
public static String insertParen(String str,int leftindex)
{
String left=str.substring(0, leftindex+1);
String right=str.substring(leftindex+1);
return left+"()"+right;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(permuteParenthesis1(3));
}
Solution 22:[22]
An attempt with memoization:
void push_strings(int i, int j ,vector<vector <string>> &T){
for (int k=0; k< T[j].size(); ++k){
for (int l=0; l< T[i - 1 - j].size(); ++l){
string s = "(" + T[j][k] + ")" + T[i-1 - j][l];
T[i].push_back(s);
}
}
}
vector<string> generateParenthesis(int n) {
vector<vector <string>> T(n+10);
T[0] = {""};
for (int i =1; i <=n; ++i){
for(int j=0; j<i; ++j){
push_strings(i,j, T);
}
}
return T[n];
}
Solution 23:[23]
def form_brackets(n: int) -> set:
combinations = set()
if n == 1:
combinations.add('()')
else:
previous_sets = form_brackets(n - 1)
for previous_set in previous_sets:
for i, c in enumerate(previous_set):
temp_string = "{}(){}".format(previous_set[:i+1], previous_set[i+1:])
combinations.add(temp_string)
return combinations
Solution 24:[24]
void function(int n, string str, int open, int close)
{
if(open>n/2 || close>open)
return;
if(open==close && open+close == n)
{
cout<<" "<<str<<endl;
return;
}
function(n, str+"(", open+1, close);
function(n, str+")", open, close+1);
}
Caller - function(2*brackets, str, 0, 0);
Solution 25:[25]
I was asked this question in an interview today.
I always skipped this question in Cracking The Coding because I thought it is a silly question for an interview. The interviewer didn't share my opinion though.
Below is the solution that I could come up with in the interview. The interviewer was looking at the more performant method that is already given above. He passed me though for this solution.
//This method is recursive. It simply returns all the possible arrangements by going down
//and building all possible combinations of parenthesis arrangements by starting from "()"
//Using only "()" for n == 1, it puts one "()" before, one "()" after and one "()" around
//each paren string returned from the call stack below. Since, we are adding to a set, the
//set ensure that any combination is not repeated.
private HashSet<string> GetParens(int num)
{
//If num < 1, return null.
if (num < 1) return null;
//If num == 1, there is only valid combination. Return that.
if (num == 1) return new HashSet<string> {"()"};
//Calling myself, by subtracting 1 from the input to get valid combinations for 1 less
//pair.
var parensNumMinusOne = GetParens(num - 1);
//Initializing a set which will hold all the valid paren combinations.
var returnSet = new HashSet<string>();
//Now generating combinations by using all n - 1 valid paren combinations one by one.
foreach (var paren in parensNumMinusOne)
{
//Putting "()" before the valid paren string...
returnSet.Add("()" + paren);
//Putting "()" after the valid paren string...
returnSet.Add(paren + "()");
//Putting paren pair around the valid paren string...
returnSet.Add("(" + paren + ")");
}
return returnSet;
}
The space complexity of other more performant solution is O(1) but for this one is O(Cn), where Cn is Catalan Number.
The time complexity of this code is same as the other high performant solution, which is same as O(Cn).
Solution 26:[26]
In javascript / nodejs.
The program was originally meant to answer the Ultimate Question, but it is just perfect to enumerate the valid brackets combinations.
function* life(universe){
if( !universe ) yield '';
for( let everything = 1 ; everything <= universe ; ++everything )
for( let meaning of life(everything - 1) )
for( let question of life(universe - everything) )
yield question + '(' + meaning + ')';
}
let love = 5;
let answer = [...life(love)].length;
console.log(answer);
function brackets(n){
for( k = 1 ; k <= n ; k++ ){
console.log(...life(k));
}
}
brackets(5);
Solution 27:[27]
public class Solution {
public IList<string> GenerateParenthesis(int n) {
List<string> combinations = new List<string>();
generateAll(new char[2 * n], 0, combinations);
return combinations;
}
public void generateAll(char[] current, int pos, List<string> result) {
if (pos == current.Length) {
if (valid(current))
result.Add(new string(current));
} else {
current[pos] = '(';
generateAll(current, pos+1, result);
current[pos] = ')';
generateAll(current, pos+1, result);
}
}
public bool valid(char[] current) {
int balance = 0;
foreach (char c in current) {
if (c == '(')
balance++;
else balance--;
if (balance < 0)
return false;
}
return (balance == 0);
}
}
Solution 28:[28]
Another Solution to handle this issue.
correct string: (){}[]
incorrect string: ([{)]}
private static boolean isEqualBracket(String str) {
Stack stack = new Stack();
if (str != null && str.length() > 0) {
for (int i = 0; i < str.length(); i++) {
char nextChar = str.charAt(i);
if (nextChar == '(' || nextChar == '{' || nextChar == '[') {
stack.push(nextChar);
} else if (nextChar == ')' || nextChar == '}' || nextChar == ']') {
char startChar = stack.peek().toString().charAt(0);
if ((startChar == '(' && nextChar == ')') || (startChar == '{' && nextChar == '}') || (startChar == '[' && nextChar == ']')) {
stack.pop();
} else {
return false;
}
} else {
return false;
}
}
} else {
return false;
}
return stack.empty();
}
Solution 29:[29]
In C#
public static void CombiParentheses(int open, int close, StringBuilder str)
{
if (open == 0 && close == 0)
{
Console.WriteLine(str.ToString());
}
if (open > 0) //when you open a new parentheses, then you have to close one parentheses to balance it out.
{
CombiParentheses(open - 1, close + 1, str.Append("{"));
}
if (close > 0)
{
CombiParentheses(open , close - 1, str.Append("}"));
}
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow