Google Interview Question
Software Engineer / DevelopersCountry: United States
The idea is simple - Recursive Backtracking
C++ program to print all valid combinations of 'n' pair of braces
#include<iostream>
#include<string>
using namespace std;
void print_parentheses(int n);
void print(int left, int right, int n, string s);
int main()
{
int n;
cout<<"Enter n: ";
cin>>n;
print_parentheses(n);
}
void print_parentheses(int n)
{
string s="";
print(0, 0, n, s);
}
void print(int left, int right, int n, string s)
{
if(left>n || right>n || right>left)
return;
if(left==right && left+right==2*n)
{
cout<<s<<endl;
return;
}
print(left+1, right, n, s+"(");
print(left, right+1, n, s+")");
}
This is a simple and intuitive solution.
But we can replace string with bit-storage.
There are (2n)!/(n!(n+1)!) total combination for parentheses and copying string is very time-consuming operation.
Here is the comparing of work time (in ms) for string and bit implimintation:
n bit string
5 0 2
10 8 869
11 28 3164
12 97 11450
13 358 (< 1 sec) 40892 (40 sec)
14 1300 (1 sec) 146235 (2 min)
15 4788 (5 sec) 537079 (8 min)
I hope, I assure you that it is bad to copy strings
class Parentheses /*save as binary */
{
public:
Parentheses() : parentheses(0), n(0) {}
Parentheses add(bool bracket) //return new object
{
if(bracket) return Parentheses(parentheses | (1 << n), n + 1);
else return Parentheses(parentheses, n + 1);
}
void print()
{
for(size_t i = 0; i<n; ++i)
if(parentheses & (1 << i)) cout<<"("; else cout<<")";
cout<<endl;
}
private:
Parentheses(unsigned long long parentheses, size_t n)
: parentheses(parentheses), n(n) {}
unsigned long long parentheses;
size_t n;
};
void find(int n, int left=0, int right=0, Parentheses s= Parentheses())
{
if(left+right==2*n)
{
s.print(); return;
}
if(left != n)
find(n, left+1, right, s.add(true));
if(right < left)
find(n, left, right+1, s.add(false));
}
the combinations of braces should be build in following lexical rules
E ::= ()
E ::= (E)
E ::= E E
we can use dp here, say dp[i] is a list of all possible combinations of i pairs of braces
for rule 1, we have dp[1] = ["()"]
for rule 2, we have dp[i+1] = each item in dp[i] cover with a braces
for rule 3, we have dp[i] = each item in dp[j] combine each item in dp[k], where j+k == i
#!/usr/bin/env python
# Implement an algorithm to print all possible valid combinations of braces
# when n pairs of parenthesis are given.
def parenthesis(n, left=0, right=0, s=""):
"""
>>> parenthesis(2)
(())
()()
"""
if left > n or right > n or right > left:
return
if left == right and left + right == 2*n:
print s
parenthesis(n, left + 1, right, s+"(")
parenthesis(n, left, right + 1, s+")")
public static void brackets(int leftCnt, int rightCnt, int totalCnt, String out) {
if(leftCnt == totalCnt && rightCnt == totalCnt) {
System.out.println(out);
return;
}
if(leftCnt < totalCnt) {
brackets(leftCnt+1, rightCnt, totalCnt, out + "(");
}
if(rightCnt < leftCnt) {
brackets(leftCnt, rightCnt+1, totalCnt, out + ")");
}
}
static void
all_forms (int level, int left, char *buf, char *ptr)
{
/* start a new nesting */
*ptr = '(';
ptr++;
left--;
if (left) {
// build whatever left as nested
all_forms(level+1, left, buf, ptr);
}
/* close this nesting - over-writing the nested buffer */
*ptr = ')';
ptr++;
/* if any iterations left, do it without nesting */
if (left) {
// build whatever left as un-nested (same level)
all_forms(level, left, buf, ptr);
} else {
// reached the end - close all nesting levels and print it
while (level) {
*ptr = ')';
ptr++;
level--;
}
*ptr = 0;
printf("%s\n",buf);
}
}
public static void validBraces(String buffer , int open , int close , int len){
if(close>open){
return;
}
if(open >=len){
int k = open-close;
while(--k>=0){
buffer+=")";
}
System.out.println(buffer);
return;
}
validBraces(buffer+")", open, close+1, len);
validBraces(buffer+"(", open+1, close, len);
}
public static String paranComb(int comb)
{
if (comb == 1)
{
return "()";
}
else
{
return paranComb(comb - 1) + "(" + paranComb(comb-1) + ")";
}
}
public static void main(String [] args)
{
System.out.println(paranComb(1));
System.out.println(paranComb(2));
System.out.println(paranComb(3));
System.out.println(paranComb(4));
}
The trick to this problem is to realize that increasing there is only 2 ways to add parans.
Start with comb = 1
()
Notice when we go to comb = 2 We prepend a new () and insert a ()
()(())
In otherwords we are prepending and inserting the previous combination.
so for comb = 3 we just add () infront comb2 and surround comb 2 with parans
()(())(()(()))
Updated
public static String paranComb(int comb)
{
if (comb == 1)
{
return "()";
}
else
{
return "()" + paranComb(comb - 1) + "(" + paranComb(comb-1) + ")";
}
}
public static void main(String [] args)
{
System.out.println(paranComb(1));
System.out.println(paranComb(2));
System.out.println(paranComb(3));
System.out.println(paranComb(4));
}
run:
()
()()(())
()()()(())(()()(()))
()()()()(())(()()(()))(()()()(())(()()(())))
Let N be an even number (just double the n from the question), the size of the thing you are building.
Backtracking: left to right build your thing. Keep track of the number of ( and ) braces already in the filled part of the thing you are building.
C:
^^^ Made N fixed compiled time constant and other things simple to make the algo. stand out as the star player.
- S O U N D W A V E October 07, 2013Made the winding and unwinding of variables explicit on purpose also (otherwise they might be "hidden" for illustrative purposes).