균형 잡힌 괄호

Question

궁금 해서요 사람이 다음 문제에 대한 역 추적 솔루션에서 생성 된 결과 수 인 내 질문에 대답 할 수있는 경우 :

괄호

감안할 때 N 쌍, 잘 형성 괄호의 모든 조합을 생성하는 함수를 작성 . 예를 들어

주어진 N = 3 솔루션 집합은 다음

"((()))", "(())", "(())()", "(()()) ","()()() "

가 유래에 관련 게시물 : Generate balanced parentheses in java

이 나에게 유효 괄호의 수를 줄 수있는 공식이있는 경우 경우 내 의심 나는 그들을 계산하기 전에 생성 할 수 있습니다. 예 :
- F (N) :
- F (1) = 1
- F (2) = 2
- F (3) = 5
등등 .. 그리고

고맙습니다.

Answer 1

정확히 일치하는 n 쌍의 괄호를 포함하는 수식은 카탈로니아 어 수를 통해 계산할 수 있습니다. 위키 백과에서 관련 link을 인용 :

는 솔루션 카탈로니아 번호에 의해 주어진다 조합론 많은 계산 문제가 있습니다 ... 내지 Cn는 길이 2N의 반다이 크 단어의 수입니다. Dyck 단어는 문자열의 초기 세그먼트가 X의 Y보다 많지 않은 nX와 nY로 구성된 문자열입니다. 기호 X를 열린 괄호로 다시 해석하고 Y를 닫는 괄호로 다시 해석하면 Cn은 표현식의 수를 계산합니다 n 개의 쌍의 괄호가 정확하게 일치합니다.

n 번째 카탈루냐어 번호로 이항 계수의 관점에서 주어진되어

: