35

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

()
(())  ()()   
((()))  (()())  (())()  ()(())  ()()()
1
  • Does anyone know why the number of well-formed 2n brackets is C(2n, n) - C(2n, n+1). I know C(2n n) is obviously over-counting so we need to subtract something but don't see how that something is C(2n, n+1)
    – user674669
    Oct 24, 2012 at 12:49

30 Answers 30

54

Took a crack at it.. C# also.

public void Brackets(int n) {
    for (int i = 1; i <= n; i++) {
        Brackets("", 0, 0, i);
    }
}

private void Brackets(string output, int open, int close, int pairs) {
    if((open==pairs)&&(close==pairs)) {
        Console.WriteLine(output);
    } else {
        if(open<pairs)
            Brackets(output + "(", open+1, close, pairs);
        if(close<open)
            Brackets(output + ")", open, close+1, pairs);
    }
}

The recursion is taking advantage of the fact that you can never add more opening brackets than the desired number of pairs, and you can never add more closing brackets than opening brackets..

10
  • 1
    nice indeed! esp leveraging the precondition opening-braces >= closing-braces.
    – aleemb
    Apr 8, 2009 at 13:36
  • 1
    @Prabhu Jayaraman - with which input will it produce invalid pairs ? The conditions restrict it to never add a closing bracket if there are not already opening brackets, so I do not think you are correct.
    – markt
    Aug 6, 2010 at 15:17
  • 1
    @Prabhu Jayaraman - why ? Please give me an example input that produces incorrect results.
    – markt
    Aug 6, 2010 at 15:46
  • OOps very sorry markt. wrong judgement. i thought close<pairs +1
    – josh
    Aug 6, 2010 at 17:16
  • 1
    Very elegant solution.. you nailed recursion!
    – satyajit
    Sep 11, 2010 at 5:37
11

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)
9

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:
()
(()) ()()
((())) (()()) (())() ()(()) ()()()

3
  • as per forum, fourth line should read output[2*pairs - 1] = ')'; not output[1] = ')';
    – aleemb
    Apr 7, 2009 at 23:26
  • @KingNestor, I made a quick edit to the code so it spits it out exactly as the OP wanted. Small change, I called Brackets() recursively which then called foo() recursively. I'm trying to shrink yours down a little right now.
    – mmcdole
    Apr 7, 2009 at 23:33
  • Yes, everyone.. feel free to help reduce this one down further. It would be nice if we could get rid of the intermediary function before the recursive call.
    – KingNestor
    Apr 7, 2009 at 23:36
9

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")

(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)
2
  • I think it may be instructive to keep it around; so often people just glance at answers, think they look good, and upvote. It serves as a reminder to be cautious. Feel free to downvote it, as it deserves it.
    – Brian
    Apr 7, 2009 at 22:57
  • Also I like the use of yield in the first post. I hadn't used it before and it's really handy though not in this particular scenario.
    – aleemb
    Apr 8, 2009 at 13:24
5

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.

2
  • Elegant! It may be fun to memoize and then compare the perf for N=12 or so.
    – Brian
    Apr 8, 2009 at 5:58
  • On my machine, a memoized version of this code (slightly modified to replace the sprintf with concatenation) runs in ~.6s for N=12, whereas your code runs in ~.2s. The difference gets worse as you go up from there, though. Some of this is due to string concatenation, which you nicely avoid.
    – kvb
    Apr 8, 2009 at 6:28
4

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")
(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)
2
  • For n=2, doesn't this print ()() twice?
    – David Z
    Apr 7, 2009 at 22:31
  • Making it a 'set' guarantees uniqueness. Nevertheless, this answer is wrong! Update forthcoming.
    – Brian
    Apr 7, 2009 at 22:43
4

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
((()))
(()())
(())()
()(())
()()()
3

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 :-)
1
  • Broken link. It's usually best to include the main snippet right in the post for this reason. Oct 1, 2016 at 22:01
3

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))))
2

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;
}
0
2

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)

2

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);
 }}
1
  • 1
    very simple solution.
    – Peter Lee
    Feb 11, 2018 at 17:37
1
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)

1

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
1

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;
    }
}
1
  • This will produce duplicate results. For example, '()' + '()()' vs. '()()' + '(). The HahSet catches them, but it's an extra data structure that's not necessary (see the top answer). Sep 17, 2015 at 1:31
1

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)")
    }
    ""
}
0

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;
}
0
//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);
        }
    }
}
0

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)
0
  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);
  }
0
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);
    }
}
1
  • When answering questions it is best to explain the code so that it can be more easily understood by other users of the site.
    – Tristan
    Nov 29, 2015 at 19:24
0

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));

}
0

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];
}
0
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
1
  • Welcome to Stack Overflow! While this code may solve the asker's problem, it would be preferable to explain how it works and what are the differences between it and what the asker has tried (if (s)he has tried anything at all) - please edit your answer to do so.
    – SE is dead
    Oct 9, 2016 at 23:18
0
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);

0

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

0

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);
0
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);
    }
}
0

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();
    }
-1

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("}"));
        }
    }
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.