Oleksandr Gavenko's blog
2017-01-18 18:30 Permutations of parentheses

Usual interview task is: Print all possible n pairs of balanced parentheses.

Recursive solution is based on constraint that number of left open parentheses should be greater than right closing.

Following code appends parentheses from the left to the right with such constraint:

def gen_aux(left, right, result):
    if left == 0 and right == 0:
        print(result)
        return
    if left > 0:
        gen_aux(left-1, right, result+"(")
    if right > left:
        gen_aux(left, right-1, result+")")

def gen(n):
    gen_aux(n, n, "")

Result of:

gen(1)
gen(2)
gen(3)
gen(4)

is:

()

(())
()()

((()))
(()())
(())()
()(())
()()()

(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
interview, problem

Feeds

all / emacs / java / python

Tags

adb(1), admin(1), android(1), anki(1), blog(1), c(1), css(2), cygwin(2), driver(1), emacs(3), fs(1), git(2), gradle(1), hardware(1), hg(2), html(1), interview(13), java(2), js(3), lang(2), lighttpd(1), mobile(1), naming(1), oracle(1), print(1), problem(5), quiz(6), rst(1), security(1), sql(2), srs(1), style(1), unit(1), utils(1), vcs(3), web(2), win(2), windows(1)

Archive