Here's another F# solution, favoring elegance over efficiency, although memoization would probably lead to a relatively well performing variant.

let rec parens = function | 0 -> [""] | n -> [for k in 0 .. n-1 do for p1 in parens k do for p2 in parens (n-k-1) -> sprintf "(%s)%s" p1 p2] 

Again, this only yields a list of those strings with exactly n pairs of parens (rather than at most n), but it's easy to wrap it.