Sunday, April 05, 2015

valid n-pairs of brackets

// n=1
()

// n=2
(())
()()

// n=3
((()))
(()())
(())()
()(())
()()()
This needs a set to avoid duplicates. Space: O(pairs)
npairs(n):
    npairs(n, new buffer(), new set())

npairs(n, out, set):
    if n == 0:
        if !set.contains(out):
            set.add(out)
            print(out)
        return
    for i=0, i <= out.length(), i++:
        out.insert(i, "()")
        npairs(n-1, out, set)
        out.remove(i, 2)

or

npairs(n):
    set pairs = new
    pairs.add("")
    for i = 0, i < n, i++:
        pairs = (pairs)
    return pairs

(ipairs):
    opairs = new
    for pair in ipairs:
        buffer = new (pair)
        for i = 0, i <= pair.length(), i++:
            buffer.insert(i, "()")
            opairs.add(buffer.tostring())
    return opairs
This does not.
npairs(n):
    npairs(n, 0, 0, new buffer())

npairs(n, left, right, out):
    if left < right:
        return
    if left == right == n:
        print(out)
        return
    if left < n:
        out.append("(")
        npairs(n, left+1, right, out)
        out.length--
    if right < n:
        out.append(")")
        npairs(n, left, right+1, out)
        out.length--

[Hat tip to ctci]

No comments:

Post a Comment