C++ の std::next_permutation の valid parens 版を作る方法をご紹介します。

後ろから見て初めて ()) の形になっている箇所を見つけて、i と置きます。すると、こういう感じのをこういう感じにすればよいので、i と i + 1 をスワップして、i + 2 以降をソートです。

i
())))))))))))))()()()()()()()()
)()))))))))))))()()()()()()()()
)((((((((()))))))))))))))))))))

ちなみにソートせずともスワップする箇所がわかるのでそれをするとよいのですが、コードが数行長くなるのと、大して速くなさそうなので割愛です。

use proconio::{fastout, input};
use std::iter::repeat;

#[fastout]
fn main() {
    input! {
        n: usize,
    }
    if n % 2 == 1 {
        return;
    }
    let mut s = repeat('(')
        .take(n / 2)
        .chain(repeat(')').take(n / 2))
        .collect::<Vec<_>>();
    loop {
        println!("{}", s.iter().collect::<String>());
        match s.windows(3).rposition(|v| v == &['(', ')', ')']) {
            None => break,
            Some(i) => {
                s.swap(i, i + 1);
                s[i + 1..].sort();
            }
        };
    }
}

提出 (6 ms): https://atcoder.jp/contests/typical90/submissions/28302847

なおですが、ブログ記事「next_permutation の解説と、それと同様のアルゴリズムで全列挙できるもの一覧 - ブログ名」に関連テクをもっと記載しております。