競プロ典型 002

https://atcoder.jp/contests/typical90/tasks/typical90_b

xy座標で原点から出発して'('をx方向に1、')'をy方向に1進む、と読み替えれば、x=yより左上に行かないようにするルートがこの問題の答えの一つずつです。カタラン数と同じですね。
先入れ先出しで素直に書けばよいです。

// Encyclopedia of Parentheses
#![allow(non_snake_case)]

use std::collections::VecDeque;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}


//////////////////// process ////////////////////

type Point = (usize, usize);
type Path = Vec<Point>;

fn nexts(pt: Point, N: usize) -> Vec<Point> {
    let mut points = vec![];
    if pt.0 < N/2 {
        points.push((pt.0+1, pt.1))
    }
    if pt.0 > pt.1 {
        points.push((pt.0, pt.1+1))
    }
    points
}

fn convert(path: &Path) -> String {
    (0..path.len()-1).map(|i| if path[i+1].0 > path[i].0 { '(' } else { ')' }).
                                                            collect::<String>()
}

fn F(N: usize) {
    if N % 2 == 1 {
        return
    }
    
    let mut q: VecDeque<Path> = VecDeque::new();
    q.push_back(vec![(0, 0)]);
    while let Some(path) = q.pop_front() {
        let pt0 = *path.last().unwrap();
        for pt in nexts(pt0, N).into_iter() {
            let mut path1 = path.to_vec();
            path1.push(pt);
            if pt.0 + pt.1 == N {
                println!("{}", convert(&path1))
            }
            else {
                q.push_back(path1)
            }
        }
    }
}

fn main() {
    let N = read();
    F(N)
}