Google Interview Question: Write a function Brackets(int... | Glassdoor

## Interview Question

Software Engineer Interview New York, NY

# Write a function Brackets(int n) that prints all

combinations of well-formed brackets. For Brackets(3) the output would be ((())) (()()) (())() ()(()) ()()()
Tags:
brain teaser, algorithm, recursive algorithm

0

public class Parenth2 {

static int total = 3;

static private void Brackets(String output, int open, int close, int pairs) {
if ((open == pairs) &amp;&amp; (close == pairs) &amp;&amp; output.length() == total * 2) {
System.out.println(output);
} else {
if (open &lt; pairs)
Brackets(output + "(", open + 1, close, pairs);
if (close &lt; open)
Brackets(output + ")", open, close + 1, pairs);
}

}

public static void main(String[] args) {
Brackets("", 0, 0, total);
}
}

Interview Candidate on May 8, 2010
0

You almost got thte answer, just a couple of errors...
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

/**
*
* @author Owner
*/
public class Parenth4 {

static private void Brackets(String output, int open, int close, int pairs, boolean opened, boolean closed, int total) {
if ((open == pairs) &amp;&amp; (close == pairs) &amp;&amp; output.length() == total * 2) {
System.out.println(output);
} else {
if ((open &lt; pairs))
Brackets(output + "(", open + 1, close, pairs,true, closed, total);
if ((close &lt; open)&amp;&amp; opened)
Brackets(output + ")", open, close + 1, pairs,opened,closed, total);
}

}

public static void Brackets(int total) {
Brackets("", 0, 0, total,false,false, total);
}
public static void main(int number){
Brackets(number);
}
}

Interview Candidate #2 on May 11, 2010
3

This is a DP/memoization question, I believe. The base case is 0 and 1 bracket (the answer is empty or (). The recurrence is:

bracket(n) =
all combination of results from bracket(n-1) and from bracket (1)
from bracket(n-2) and bracket(2)
.
.
from bracket(1) and bracket(n-1)
lastly, '(' . bracket(n-1) ')'

The DP version of the above recurrence is straightforward. (Btw, this recurrence obviously will produce duplicate, but it's not hard to produce a modification that does not produce duplicate.) ;)

shards on May 11, 2010
1

Here is a F# implementation:

let rec Br total output openp closep =
if openp = total &amp;&amp; closep = total
then
printfn "%s" output
else
if openp &lt; total then Br total (output + "( ") (openp + 1) closep
if closep &lt; openp then Br total (output + " )") openp (closep + 1)

let Brackets total =
Br total "" 0 0

Brackets 5

Horia on May 13, 2010
0

void parens(int nPairs) {
parens("", nPairs, nPairs);
}

void parens(string ans, int leftCount, int rightCount) {
if (leftCount==0 &amp;&amp; rightCount==0) {
cout 0) {
parens(ans+"(", leftCount-1, rightCount);
}
if (rightCount&gt;leftCount) {
parens(ans+")", leftCount, rightCount-1);
}
}

marcos on May 17, 2010
1

To Remove duplicates simply use java Set :)

public static String bracket(int a) {

Set s = new TreeSet();
bracketIntern(s, a, "", "");
System.out.println(s);
return s.toString();
}

public static void bracketIntern(Set set,int a, String preFix,String suffix) {
if(a == 1) {
return;
}
bracketIntern(set, a-1, preFix+"()", suffix);
bracketIntern(set, a-1, preFix+"(", ")"+suffix);
bracketIntern(set, a-1, preFix, "()"+suffix);
}

Rohan Dhapodkar on May 21, 2010
0

I think you can also build a trie, and the traverse the trie to print out all the combinations.

somebody on Jul 20, 2010
1

Complete python program to print the all combinations of well-formed brackets.

How to calculate its Big-o?
The recursive recurrence seems a little bit complicated.

----
def brackets(n):
sol = []
li = [' ' for x in range(n*2)]
def recu_brackets(opened, closed):
if n - opened:
li[opened + closed] = '('
recu_brackets(opened + 1, closed)
if n - closed and opened &gt; closed:
li[opened + closed] = ')'
recu_brackets(opened, closed + 1)
if opened == n and closed == n:
sol.append(''.join(li))
recu_brackets(0, 0)
print ' '.join(sol)

brackets(3)

userisyo on Aug 19, 2010
1

wasn't all that neat. o well

public class MakeBrackets{
static List make(int number){

if (number == 0) {list.add(""); return list;}
if (number == 1) {list.add("()"); return list;}

for (int i = 0; i &lt; number; i++){
for (String item : make(i)){
for (String item2 : make(number - 1 - i)){
list.add("(" + item + ")" + item2);
}
}
}
return list;
}

public static void main(String[] args){
System.out.println(make(Integer.parseInt(args[0])));
}
}

xster on Aug 25, 2010
0

def brackets(n):
return bracketsPrefix("", n, n)

def bracketsPrefix(prefix, opens, closes):
total = 0
assert opensopens:
total += bracketsPrefix(prefix+")", opens, closes-1)
if opens&gt;0:
total += bracketsPrefix(prefix+"(", opens-1, closes)

if __name__=="__main__":
for i in range(6):
n = brackets(i)
print i,n
x = raw_input("** ")

anon on Jun 1, 2011
0

This question gets so popular and I found this article has a really good explanation: https://goo.gl/E0m0EC

Jack on Dec 22, 2016