Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
12
of 12 vote

The code prints all forms without duplicates. This question (solution) is in "Cracking the coding interview" Book.

``````def paren(left,right,string):
if(left == 0 and right == 0):
print string
if(left>right):
return
if (left > 0):
paren(left-1,right,string+"(")
if (right > 0):
paren(left,right-1,string+")")

def parentheses(n):
paren(n/2,n/2,"")

parentheses(6)``````

output:
((()))
(()())
(())()
()(())
()()()

Comment hidden because of low score. Click to expand.
0

This solution is beautiful.

Comment hidden because of low score. Click to expand.
3
of 3 vote

C version:

``````#include <stdio.h>
#include <stdlib.h>
#define MAX 20

int n, kind;
char s[MAX*2+1];
/*
we can recursively determine next character of the string
if left < n
we can choose to use one more left parenthesis or not
if right < left
we use one more right parenthesis
*/
void print(char* dest, int left, int right)
{
if(left == n && right == n){
puts(dest);
++kind;
return;
}
if(left < n){
dest[left+right] = '(';
print(dest, left+1, right);
}
if(right < left){
dest[left+right] = ')';
print(dest, left, right+1);
}
}

int main()
{
while(scanf("%d", &n), n){
s[n<<1] = '\0';
kind = 0;
print(s, 0, 0);
printf("%d kinds in total\n", kind);
}

return 0;
}``````

Comment hidden because of low score. Click to expand.
0

first call need be print(s, 1, 0); or else can't recursive...

Comment hidden because of low score. Click to expand.
1
of 1 vote

Recursive version.

Keep track of how many open and close brackets are remaining.

Also keep track of number of open - number of closed used so far (called the balance_factor).

Python code:

``````def paren(num_open, num_close, balance_factor, paren_list):
if num_open + num_close == 0:
print "".join(paren_list)
return

if balance_factor > 0 and num_close > 0:
paren_list.append(")")
paren(num_open, num_close-1, balance_factor-1, paren_list)
paren_list.pop()

if num_open > 0:
paren_list.append("(")
paren(num_open -1, num_close, balance_factor+1, paren_list)
paren_list.pop()

def paren_gen(n):
print "n =", n
paren(n, n, 0, [])
print "-----"

def main():
paren_gen(2)
paren_gen(3)
paren_gen(4)

if __name__ == "__main__":
main()``````

output

``````n = 2
()()
(())
-----
n = 3
()()()
()(())
(())()
(()())
((()))
-----
n = 4
()()()()
()()(())
()(())()
()(()())
()((()))
(())()()
(())(())
(()())()
(()()())
(()(()))
((()))()
((())())
((()()))
(((())))
-----``````

Comment hidden because of low score. Click to expand.
0

balance_factor = num_close - num_open

so we don't exactly need to pass that around. Makes it easier to read though.

Comment hidden because of low score. Click to expand.
0

And here is the same code using generators (note that will multiply time complexity by n or n^2, depending on implementation).

``````def paren(num_open, num_close, balance_factor, paren_list):
if num_open + num_close == 0:
yield  "".join(paren_list)

if balance_factor > 0 and num_close > 0:
paren_list.append(")")
for s in paren(num_open, num_close-1, balance_factor-1, paren_list):
yield s
paren_list.pop()

if num_open > 0:
paren_list.append("(")
for s in paren(num_open -1, num_close, balance_factor+1, paren_list):
yield s
paren_list.pop()

def paren_gen(n):
print "n =", n
for s in paren(n, n, 0, []):
print s
print "-----"

def main():
paren_gen(2)
paren_gen(3)
paren_gen(4)

if __name__ == "__main__":
main()``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The code above looks correct. I am still posting the java version I wrote using a similar approach. The recursive implementation is in fact dynamic programming.

``````public class ParanthesisSequence {
public static void GetSequence(int N, int nClose) {
if (N == 0) {
return;
}
if (nClose == 0) {
// We don't have to close any paranthesis since there are no open ones
a_sequence = a_sequence + "(";
GetSequence(N - 1, 1);
}
if (nClose > 0) {
if (N >= nClose + 2) {
// We could still open paranthesis
String temp = a_sequence;
a_sequence = a_sequence + "(";
GetSequence(N - 1, nClose + 1);
a_sequence = temp;
}
a_sequence = a_sequence + ")";
GetSequence(N - 1, nClose - 1);
}
}

private static String  a_sequence = "";
public static ArrayList<String> sequences;
}``````

Sample usage:

``````public static void main(String[] args) {
// TODO code application logic here
int N = 6; // N = 2 * n
ParanthesisSequence.sequences = new ArrayList<String>();
ParanthesisSequence.GetSequence(N, 0);
for (String s : ParanthesisSequence.sequences) {
System.out.println(s);
}
}``````

Output:

``````((()))
(()())
(())()
()(())
()()()``````

Comment hidden because of low score. Click to expand.
0

Problem with this is the huge space usage (which is not the case with the python solution above).

Comment hidden because of low score. Click to expand.
0

(And that is something the interviewer will be worried about).

Comment hidden because of low score. Click to expand.
0

Of course, since there is probably a super-polynomial number of terms. I could as well print the sequence out instead of adding it to the list. Either way, writing it to console does not resolve the space problem.

Comment hidden because of low score. Click to expand.
0

The total number is Catalan number (call it C_n).

And no, space usage being O(n) and that is relevant.

For example, instead of printing it, all I would have to do is yield it (a python feature for creating generators).

Now I have a generator which can do something similar to hasNext(), next() of Java. It would use only O(n) space, and can be used to print out only the first 1000 arragements or 10000 or whatever. The space usage will remain O(n) irrespective of how many times you do a next.

The fact that I am printing it is not any indication that the space usage will be Omega(C_n).

Of course, now that I look at your solution more carefully, you don't really need to use that much space and our solutions are quite similar. So actually that is not a problem with your solution and can potentially be converted into a hasNext, next generator using O(n) space.

Comment hidden because of low score. Click to expand.
0

See update to my answer using generators.

Comment hidden because of low score. Click to expand.
0

Thanks for the reference to Cn and generators in python. I guess I see your point.
I believe one way to modify my implementation to work as a generator is to store the state after each call (e.g., sequence and the last value of "N" and "nClose" before finding a new sequence).

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class NBrackets{

public static void main( String[] args ){
sumCombination( "", Integer.parseInt( args[0] ) );
}

static void sumCombination( String output, int sum ){
if( sum == 0 ) {
generateOutput( output );
return;
}

for( int i = 1; i <= sum; i++ ){
sumCombination( output + i, sum - i );
}
}

static void generateOutput( String output ){
StringBuilder builder = new StringBuilder();

for( int i = 0; i < output.length(); i++){
char c = output.charAt( i );
builder.append( toBrackets( c - 48 ) );
}

System.out.println( builder.toString() );
}

static String toBrackets( int n ){
StringBuilder builder = new StringBuilder();
for( int i = 0; i < n; i ++ ){
builder.append( "(" );
}
for( int i = 0; i < n; i ++ ){
builder.append( ")" );
}

return builder.toString();
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python code below:

``````def R(n, buf=''):
if len(buf) == 2*N:
print buf

if n > 0:
buf += ')'
R(n-1, buf)
buf=buf[:-1]

if 2*N - (n+len(buf)) >= 2:
buf += '('
R(n+1, buf)
buf=buf[:-1]

N = 4
R(0)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<stdio.h>
#include<stdlib.h>
void printParanthesis(char *str,int index,int num,int open,int close)
{
if( open==close&&open==num)
{
printf("\n %s",str);
return;
}

if(open<num)
{

str[index]='(';
printParanthesis(str,index+1,num,open+1,close);

}

if(open>close)
{

str[index]=')';
printParanthesis(str,index+1,num,open,close+1);

}
}
int main()
{

char str[50]={'\0'};
printParanthesis(str,0,3,0,0);

}``````

Comment hidden because of low score. Click to expand.
0

nice one

Comment hidden because of low score. Click to expand.
0
of 0 vote

Another C Program using "BackTracking"

``````#include<stdio.h>

#define MAXN 100
#define MAXC 3

char a[MAXN];
char c[MAXC];

int is_solution(char a[], int k, int n)
{
return (k == n-1);
}

void process_solution(char a[], int k, int n)
{
a[k+1] = '\0';
printf("\n%s",a);
}

int construct_candidates(char a[], int k, int n, char c[])
{
int nopen = 0;
int nclosed = 0;
int ncandidates = 0;

int i=0;
for(i=0;i<k;i++)
{
if( a[i] == '(' )
{
nopen++;
}
else
if(a[i] == ')' )
{
nclosed++;
}
}

if( nopen < (n>>1) )
c[ ncandidates++] = '(';

if( nclosed < nopen )
c[ ncandidates++] = ')';

return ncandidates;
}

void backtrack(char a[], int k, int n)
{
if( is_solution( a,k, n ) )
{
process_solution(a,k,n);
return;
}
else
{
char c[MAXC];
k = k+1;
int ncandidates = construct_candidates(a,k,n,c);
int i = 0;
for(i=0; i<ncandidates; i++)
{
a[k] = c[i];
backtrack(a,k,n);
a[k] = '\0';
}
}
}

int main()
{
int n;
scanf("%d",&n);
backtrack(a,-1,n<<1);
printf("\n");
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void generateValidParanthesis(int n, String s) {
if(n == 0) { System.out.println(s); return; }

String s1 = "(" + s + ")";
String s2 = "()" + s;
String s3 = s + "()" ;

if(!s1.equals(s2) && !s1.equals(s3)) {
generateValidParanthesis(n-1, s1 );
}
if(!s2.equals(s3)) {
generateValidParanthesis(n-1, s2);
}

generateValidParanthesis(n-1,  s3 );

}``````

Comment hidden because of low score. Click to expand.
0

Call it like generateValidParanthesis(4, "");

Comment hidden because of low score. Click to expand.
0

I've came with similar solution in Objective-C, but then have realised that it doesn't generate `(())(())` when n equals 4. Probably your code also doesn't handle this case...

Comment hidden because of low score. Click to expand.
0
of 0 vote

1.define an int , i1, with n length bit initialized to 0
2.flip i1 to acquire i2
3. Starting from i2 , you read the two ints
bit by bit, print a left paran for a set bit and a right paran for an unset.
4. Increment i1, if the highest bit is still 0, print a line separator and loop back to step 2

Comment hidden because of low score. Click to expand.
0

Can you explain more? What do you do in step 4 "if the highest bit is not 0"?

Comment hidden because of low score. Click to expand.
0
of 0 vote

1.define an int , i1, with n length bit initialized to 0
2.flip i1 to acquire i2
3. Starting from i2 , you read the two ints
bit by bit, print a left paran for a set bit and a right paran for an unset.
4. Increment i1, if the highest bit is still 0, print a line separator and loop back to step 2

Comment hidden because of low score. Click to expand.
0
of 0 vote

Another C++ version

``````#include <algorithm>
#include <cmath>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

/* Main Code Starts from here */

void bracketPermut(vector<vector<char> >& vii, vector<char>& vi, int l, int r, int n) {
if(l>n)
return;
if(r == n) {
vii.push_back(vi);
return ;
}
else {
if(l>r) {
vi.push_back(')');
bracketPermut(vii, vi, l, r+1, n);
vi.pop_back();
}
vi.push_back('(');
bracketPermut(vii, vi, l+1, r, n);
vi.pop_back();
}
}

vector< vector <char> > bracketPermut(int n) {
vector <vector<char> > vii;
vector<char> vi;
bracketPermut(vii, vi, 0, 0, n);
return vii;
}

int main() {

vector< vector<char> > out = bracketPermut(5);
for(auto i: out) {
for(auto j:  i)
cout << j << " ";
cout<< endl;
}
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def gen(n, left=0, right=0,index=0,str=""):

if index == 2*n:
print(str)
return

if left < n:
gen(n, left+1, right, index+1, str+"(")

if right < left:
gen(n, left, right+1, index+1, str+")")``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def generateParenComb(left, right, left_stack, output):
if right == 0:
print output
if left > 0:
generateParenComb(left-1, right, left_stack+1, output+'(' )
if right>0 and left_stack>0:
generateParenComb(left, right-1, left_stack-1, output+')')

def topGenerateParenComb(num):
generateParenComb(num, num, 0, "")

topGenerateParenComb(4)``````

output:
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

Comment hidden because of low score. Click to expand.
0
of 0 vote

anyone knows the complexity?

Comment hidden because of low score. Click to expand.
0

2^n exponential..since at every 2n places there are 2 choices to be made.

Comment hidden because of low score. Click to expand.
0

The total number is the nth Catalan number: (2n Choose n)/(n+1).

The compexity of this is Theta(4^n/n^(1.5))

@shivkalra: There aren't 2 choices at every step. It could be any of 0, 1 or 2 choices.

Comment hidden because of low score. Click to expand.
0

shivkalra1 was close

he used a different n
in this problem there are 2n parentheses

so 2^(2n) is number of possible parentheses without regard to balancing them

which is 4^n

so it is O(4^n)

But Subbu have tighter bound for it by dividing by n^1.5, which is basically adjusting for only including balanced results.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````ArrayList<String> pairs(int n){
return pairs(n, n, "");
}
ArrayList<String> pairs(int open, int close, String s){
ArrayList<String> ret = new ArrayList<String>();
if(open == 0){
for(int i = 0; i<close; i++){
s += ")";
}
} else{
if(close > open){
}
}
return ret;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import unittest

def paren(n):
if n == 0: yield ""
for i in xrange(n):
for j in paren(i):
for k in paren(n - i - 1):
yield j + "(" + k + ")"

def generate(n):
print("Generating: 2 * {}".format(n))
for s in paren(n):
if len(s) == 2 * n:
print(s)

class Test(unittest.TestCase):
def test_generate(self):
generate(0)
generate(1)
generate(2)
generate(3)

if __name__ == "__main__":
unittest.main()``````

Comment hidden because of low score. Click to expand.
0

unittest which really does not do any testing?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class ParanTest {
public static void main(String[] args) {
buildParan(new StringBuilder(), 0, 0, 3);
}

public static void buildParan(StringBuilder sb, int open, int close, int tot){
if(close < open){
StringBuilder newSb = new StringBuilder(sb.toString());
newSb.append(')');
int newClose = close;
if(++newClose == tot){
System.out.println(newSb.toString());
}
else{
buildParan(newSb, open, newClose, tot);
}
}

if(open < tot){
int newOpen = open+1;
sb.append('(');
buildParan(sb, newOpen, close, tot);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class AllBrackets {

public static void main(String... a) throws Exception {
printAll(Integer.parseInt(a[0]));
}

public static void printAll(int n) {
printAll(new char[2 * n], 0, 0);
}

private static void printAll(char[] c, int index, int level) {
if (index >= c.length) {
System.out.println(new String(c));
return;
}
if (level > 0) {
c[index] = ')';
printAll(c, index+1, level-1);
}
if (c.length - index > level) {
c[index] = '(';
printAll(c, index+1, level+1);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php

function printParanthesis(array \$str,\$index,\$num,\$open,\$close)
{
if(\$open == \$close && \$open == \$num)
{
echo implode("",\$str)."\n";
return;
}

if(\$open < \$num)
{
\$str[\$index]='(';
printParanthesis(\$str,\$index+1,\$num,\$open+1,\$close);
}

if(\$open > \$close)
{
\$str[\$index]=')';
printParanthesis(\$str,\$index+1,\$num,\$open,\$close+1);
}
}

//main
\$str = array();
\$n = trim(fgets(STDIN));
printParanthesis(\$str,0,\$n,0,0);

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````<?php

function printParanthesis(array \$str,\$index,\$num,\$open,\$close)
{
if(\$open == \$close && \$open == \$num)
{
echo implode("",\$str)."\n";
return;
}

if(\$open < \$num)
{
\$str[\$index]='(';
printParanthesis(\$str,\$index+1,\$num,\$open+1,\$close);
}

if(\$open > \$close)
{
\$str[\$index]=')';
printParanthesis(\$str,\$index+1,\$num,\$open,\$close+1);
}
}

//main
\$str = array();
\$n = trim(fgets(STDIN));
printParanthesis(\$str,0,\$n,0,0);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>

using namespace std;

void allPatterns(string str, int n, int open, int close){
string str1, str2;
str1 = str;
str2 = str;
if(n == 0){
if((open - close) == 0)
cout<<str<<"\n";
return;
}
else if((open - close) < 0)
return;
else{
str1.append(1,'(');
allPatterns(str1,--n,open+1,close);
str2.append(1,')');
allPatterns(str2,n,open,close+1);
}
return;
}

int main(){
int open = 0, close = 0;
string str;
int n = 6;
allPatterns(str,n,open,close);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The following algorithm uses the recursive formula to generate Catalan Numbers.

``````public class Catalan{
public ArrayList< ArrayList< String> > allCatalanParentheses;

public Catalan( int n ){
for( int i = 0; i <= n; i ++ )
}

public void generate( int n ){
for( int k = 1; k < n; k ++ ){
if( allCatalanParentheses.get( k ).size() == 0 ){
generate( k-1 );
}
if( allCatalanParentheses.get( n - k ).size() == 0 ){
generate( n - k );
for( int i = 0; i < allCatalanParentheses.get( k-1 ).size(); i ++ ){
for( int j = 0; j < allCatalanParentheses.get( n-k ).size(); j ++ ){
allCatalanParentheses.get( n ).add( "(" + allCatalanParentheses.get( k-1 ).get( i ) + ")" + allCatalanParentheses.get( n-k ).get( j ) );
}
}
}
}

public void print( int k ){
for( int i = 0; i < allCatalanParentheses.get( k ).size(); i ++ )
System.out.println( allCatalanParentheses.get( k ).get( i ) );
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This one uses grammar to generate

``````#include <iostream>
#include <list>
#include <string>
using namespace std;

list<string> allParens2n(int n)
{
list<string> allParens(int n);

return allParens(2*n);
}

//Direct implementation of B -> "" | B(B)
//Which is the unambiguous grammar of balanced parenthese
list<string> allParens(int n)
{
list<string> returnValue;
if(n == 0)
{
string s("");
returnValue.push_back(s);
return (returnValue);
}

for(int i = 0; i <= (n-2);i+= 2)
{
list<string> l = allParens(i);
list<string> r = allParens(n-2-i);
for(list<string>::iterator li = l.begin();li != l.end();li++)
for(list<string>::iterator ri = r.begin();ri != r.end();ri++)
{
string s("");
s+=*li;
s+="(";
s+=*ri;
s+=")";
returnValue.push_back(s);
}
}

return returnValue;
}

int main ()
{
list<string> l = allParens2n(4);
for(list<string>::iterator i = l.begin(); i != l.end();i++)
{
cout<<*i<<"\n";
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby 2.0.0 implementation using a binary tree

``````OUTPUT = []
N=2

# creates a binary tree where left adds ( and right adds )
def search node
# stop condition on the height of the tree
if node.size >= 2*N
# Add to valid output if it's valid
OUTPUT << node if valid_answer node
return node
else
# go left and go right adding the char
left = search node+'('
right = search node+')'
end
end

# Verify if it's a valid leef
# temporary because we need to destroy the answer

# keep closing parentesis
while temp.include? "()"
# remove closed parentesis
temp.slice! "()"
end

# if there's no more char the all parentesis are valid
if temp.size == 0
return true
else
return false
end
end

# Start tree
search ""

# output
puts OUTPUT``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static void printAllParenthessis(int n, int openPar, int closePar, string currStr)
{
if (2 * n == currStr.Length)
{
Console.WriteLine(currStr);
}
if (openPar - closePar <= (2 * n - currStr.Length) / 2)
{

string newStr = currStr+"(";
printAllParenthessis(n, openPar+1, closePar, newStr);
}
if (closePar < openPar)
{
string newStr = currStr + ")";
printAllParenthessis(n, openPar, closePar + 1, newStr);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void Trace(std::vector<std::string> & rs, std::string cur, int left, int right, int n) {
if (left == n) {
cur.append(n - right, ')');
rs.push_back(cur);
} else {
Trace(rs, cur + "(", left + 1, right, n);
if (left > right) {
Trace(rs, cur + ")", left, right + 1, n);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ Solution:

#include<iostream>
using namespace std;
int n;
void f(int o,int c,string t){
if(o==n && c==n){cout<<t<<"\n";}
else{
if(o+1<=n && o+1-c>=0){f(o+1,c,t+'(');}
if(c+1<=n && o-c-1>=0){f(o,c+1,t+')');}
}
}
int main(){
cin>>n;cout<<"\n\n";
string t;f(0,0,t);
}

However this is a recursive solution.. I'm wondering if we can use memorization to solve it for a better time complexity...

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python recursive implementation

``````def gen_valid_par(p, length, para_hist):
if length < 0 or para_hist < 0:
return -1

if para_hist > length:
return -1

if length == 0 and para_hist == 0:
print p
return 1

return gen_valid_par(p + '(', length - 1, para_hist + 1) + gen_valid_par(p + ')', length - 1, para_hist - 1)

def main():
n = int(raw_input())
gen_valid_par("", 2*n, 0)

if __name__ == "__main__":
main()``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

In the following
{...} means "a set of the elements ..."
where S = {...}, s is a string
S + s means the set of each of elements of S concatenated with s
s + S means the set of s concatenated with each of the elements of S
s1 + S + s2 means the s1 concatenated with each of the elements of S concatenated with s2

For n = 0 we have S0 == {}
For n = 1 we have S1 == {()}
For n > 1 we have Sk == {Sk-1 + (), () + Sk-1, ( + Sk-1 + )}

This is very easy to write in Scala as follows:

``````def parens(l:Int):Set[String] = {
l match {
case 0 => Set.empty
case 1 => Set("()")
case _ => (for (a <- parens(l-1)) yield Set("()" + a, a + "()", "(" + a + ")")).flatten
}
}``````

To pretty print the results is similarly simply:

``def pparens(l:int):Unit = parens (l) foreach println``

For example:

``````scala> pparens(0)

scala> pparens(1)
()

scala> pparens(2)
()()
(())

scala> pparens(3)
(()())
((()))
()()()
(())()
()(())

scala> pparens(4)
(()()())
(()())()
((()()))
(()(()))
((()))()
(((())))
()(()())
()(())()
()((()))
()()(())
()()()()
(())()()
((())())

scala>``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void print(int n) {
vector<char> par(2 * n);
int noOpen = 0, noClosed = 0;

function<void(int)> back = [&](int k) {
if(k == 2 * n) {
for(int i = 0; i < par.size(); i++)
cout << par[i];
cout << endl;
}
else {

if(noOpen - noClosed < 2 * n - k) {
par[k] = '(';
noOpen++;
back(k + 1);
noOpen--;
}

if(noClosed < noOpen) {
par[k] = ')';
noClosed++;
back(k + 1);
noClosed--;
}
}
};

back(0);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple c# implmentation

``````using System;

public class Test
{
public static void Main()
{
int val = 3;
char[] ch = new char[val * 2];
PrintValidParanthesis(ch, val, val, 0);
}

public static void PrintValidParanthesis(char[] str, int left, int right, int count)
{
if (count == str.Length) { PrintParanthesis(str); return; }

if (left != 0)
{
str[count] = '(';
PrintValidParanthesis(str, left - 1, right, count + 1);
}

if (left < right)
{
str[count] = ')';
PrintValidParanthesis(str, left, right - 1, count + 1);
}

}

public static void PrintParanthesis(char[] str)
{
Console.WriteLine(str);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python

``````# number of left and right parenthesis not used yet
def foo(left,right):
if left==0:
temp = [')' for i in range(right)]
return [''.join(temp)]

if left==right:
lst = foo(left-1,right)
#what if lst == []
return ['('+x for x in lst]
else:
lst1 = foo(left-1,right)

lst2 = foo(left,right-1)
l1= ['('+x for x in lst1]
l2=[')'+x for x in lst2]
return l1+l2

if __name__ == '__main__':
for string in foo(3,3):
print string``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
public static void printValidParens(int k) {
printValidParens("", k, k);
}

private static void printValidParens(String prefix, int open, int close) {
if (open == 0 && close == 0) {
System.out.println(prefix);
return;
}

if (open >= 1) printValidParens(prefix + "(", open - 1, close);
if (close > open) printValidParens(prefix + ")", open, close - 1);
}
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
public static void printValidParens(int k) {
printValidParens("", k, k);
}

private static void printValidParens(String prefix, int open, int close) {
if (open == 0 && close == 0) {
System.out.println(prefix);
return;
}

if (open >= 1) printValidParens(prefix + "(", open - 1, close);
if (close > open) printValidParens(prefix + ")", open, close - 1);
}
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````Set<String> genBrackets(int n) {
if (n == 1) {
return Collections.singleton("()");
} else {
Set<String> subs = genBrackets(n - 1);
Set<String> retval = new HashSet<>();
for (String s : subs) {
}

return retval;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void GenerateValidParenthesis(std::string& s, int open, int close, int n)
{
if (close == n)
{
std::cout << s << std::endl;
}

if (open > close)
{
GenerateValidParenthesis(s + ')', open, close + 1, n);
}

if (open < n)
{
GenerateValidParenthesis(s + '(', open + 1, close, n);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def print_all_parenthesis(stack, history, iterations_left):

if iterations_left == 0:
if not stack:
print(history)

else:
if not stack:
print_all_parenthesis(stack + [1], history + '(', iterations_left - 1)
else:
print_all_parenthesis(stack + [1], history + '(', iterations_left - 1)
print_all_parenthesis(stack[:-1], history + ')', iterations_left - 1)

def wrapper(n):
print_all_parenthesis([], '', n * 2)

wrapper(4)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

A JavaScript solution

``````function _nParens(number){
if(number < 1){
return [];
}
if(number === 1){
return ["()"];
}

var holder = [];

var prevParenthesis = nParens(number - 1);
for(var i = 0; i < prevParenthesis.length; i++){
var parenthesisAtIndex = prevParenthesis[i];

for(var j = 0; j <= parenthesisAtIndex.length; j++){
var left = parenthesisAtIndex.slice(0, j);
var right = parenthesisAtIndex.slice(j, parenthesisAtIndex.length);
holder.push(`\${left}()\${right}`);
}
}

return holder;
}

function nParens(number){
var res = _nParens(number);
return Array.from(new Set(res))
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.