균형 잡힌 괄호 표현은 모든 종류의 괄호 쌍을 올바른 순서로 함께 포함하는 표현입니다. 이것은 모든 여는 괄호에 대해 괄호의 적절한 순서로 닫는 괄호가 있음을 의미합니다. 예:{ }.
표현 - {([][]{})({}[]{})}
출력 - 균형
이제 이 문제에서는 주어진 수의 대괄호에서 가능한 모든 균형 잡힌 식을 만들어야 합니다. 그리고 조건은 주어진 위치에 여는 대괄호가 있어야 한다는 것입니다.
이 문제에서는 정수 n과 길이가 2n인 괄호의 위치 배열이 주어지고 여는 괄호로 표시된 위치가 여는 괄호 '가 되도록 길이 2n의 균형 식의 수를 찾아야 합니다. {'.
예 -
Input : n = 2 , position [1, 0 , 0 , 0].
Output : 2
Explanation : All possible outcomes are : {{}} , {}{}. 알고리즘
-
1이 있는 모든 위치는 여는 괄호입니다.
-
다음 규칙을 사용하여 재귀 루프를 사용합니다.
-
( 여는 괄호의 개수 - 닫는 괄호의 개수 )> 0이면 0을 반환합니다.
-
n까지 반복한 후 푸시 및 팝 이후의 총 괄호가 0이면 1을 반환합니다. 즉, 얻은 솔루션입니다. 그렇지 않으면 0을 반환합니다.
-
표현식에 1이 미리 할당된 경우 인덱스를 증가시키면서 재귀적으로 호출하고 총 대괄호 수를 늘립니다.
-
그렇지 않으면 인덱스 위치에 여는 대괄호를 삽입하여 함수를 재귀적으로 호출한 다음 닫은 대괄호를 삽입하고 전체 대괄호 수를 줄이고 다음 인덱스로 이동합니다.
-
프로그램
#include <bits/stdc++.h>
using namespace std;
int find(int index, int openbrk, int n, int expression[]){
if (openbrk < 0)
return 0;
if (index == n){
if (openbrk == 0)
return 1;
else
return 0;
}
if (expression[index] == 1) {
return find(index + 1, openbrk + 1, n, expression);
} else {
return find(index + 1, openbrk + 1, n, expression) + find(index + 1, openbrk - 1, n, expression);
}
}
int main() {
int n = 3;
int expression[6] = { 1, 0, 1, 0, 0, 0};
cout << find(0, 0, 2 * n, expression) <<endl;
return 0;
}