# Print combinations of balanced parentheses

Solved the below problem. Would love to hear your feedback, especially on performance improvements (granted, the solution should remain recursive).

Especially concerned about the obj.include? elem check I had to add to prevent duplicates. Don't know a better way to do without it.

# Implement an algorithm to print all valid (e.g., properly
# opened and closed) combinations of n-pairs of parentheses.
# EXAMPLE
# Input: 3
# Output: ((())), (()()), (())(), ()(()), ()()()

def brackets(n)
return ["()"] if n == 1

brackets(n-1).each_with_object([]) do |p, obj|
for i in 0..p.length
# stuff the "()" in every possible position within 'p'
elem = p.dup.insert(i, "()")
obj << elem unless obj.include? elem
end
end
end


It's a nice solution!

One thing that might speed things up a little would be to use a Set; no need for the include? then. Just call to_a on it at the end (or don't, and return a Set - still fits the task).

Also, I'd use p.length.times { |i| ... } instead of a for loop, and make a couple of variable names a little more descriptive (p, for instance, is not a very descriptive name).

require 'set'

def brackets(n)
return ["()"] if n == 1

brackets(n-1).each_with_object(Set.new) do |str, set|
str.length.times do |i|
set << str.dup.insert(i, "()")
end
end.to_a
end


Or, without converting to an array:

def brackets(n)
return Set.new(["()"]) if n == 1

brackets(n-1).each_with_object(Set.new) do |str, set|
str.length.times do |i|
set << str.dup.insert(i, "()")
end
end
end

brackets(3) # => #<Set: {"()()()", "(())()", "()(())", "(()())", "((()))"}>


Might also be nice to avoid the duplicated "()" string. You could make it an argument, so the method can be used for other "pairs", e.g:

def brackets(n, pair = "()")
return Set.new([pair]) if n == 1

brackets(n-1, pair).each_with_object(Set.new) do |str, set|
str.length.times do |i|
set << str.dup.insert(i, pair)
end
end
end

brackets(3, "<>") # => #<Set: {"<><><>", "<<>><>", "<><<>>", "<<><>>", "<<<>>>"}>


Or you can simply make it a constant, like SINGLE_PAIR = "()".freeze.

• Ah, excellent suggestion on the use of a Set! Thanks! Apr 18, 2017 at 9:00