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

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

Recursive solution is based on constraint that number of left open parentheses should be greater then right closing. Appending parentheses from left to 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

admin(1), anki(1), blog(1), css(2), cygwin(2), emacs(3), fs(1), git(2), gradle(1), hg(2), html(1), interview(11), 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)

Archive