文字処理は Data.Text が早い

競プロ典型 90 問 2 日目 - Encyclopedia of Parentheses（★3）

{-# LANGUAGE OverloadedStrings #-}

import Data.Ix
import qualified Data.Text as T
import qualified Data.Text.IO as TI

main = sol <$> readLn >>= mapM_ TI.putStrLn

sol n
  | odd n     = [""]
  | otherwise = go n 0 ""
  where
  go 0 0 s = [s]
  go 0 _ _ = []
  go i j s
    | (0,n `div` 2) `inRange` j = go (pred i) (succ j) (s<>"(")++go (pred i) (pred j) (s<>")")
    | otherwise                 = []