leetcode:Generate Parentheses
n을 정해서 n에 대한 합법적인 괄호를 구하세요.
예를 들어 n = 3
((())) , (())() , ()()() , ()(()), (()())
2. 분석
이 문제는 사실 카틀란드 수이다. 만약 몇 쌍이 있느냐고 물으면 카틀란드 공식을 직접 이용하여 직접 구할 수 있지만 이 문제는 모든 일치 상황을 구해야 한다.
일반적으로 귀속적인 방법을 사용하는데, 왜냐하면 하위 문제로 귀결되어 조작할 수 있기 때문이다.매번 귀속 함수에 왼쪽 괄호와 오른쪽 괄호의 사용 수량을 기록한 다음 두 가지 선택이 있습니다. 하나는 왼쪽 괄호를 놓는 것이고, 다른 하나는 오른쪽 괄호를 놓는 것입니다.나머지 중괄호는 왼쪽 중괄호보다 많을 수 없거나 왼쪽 중괄호의 오른쪽 중괄호 수는 0보다 크다.정상적인 종료 조건은 좌우 괄호 수량이 모두 n이다.
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
if(n>0)
Brackets(n,"",0,0,ans);
return ans;
}
void Brackets(int n, string str,int left,int right, vector<string> &ans) {
if(left==n){
ans.push_back(str.append(n-right,')'));
return;
}
Brackets(n,str+'(',left+1,right,ans);
if(left>right)
Brackets(n,str+')',left,right+1,ans);
}
};
class Solution {
public:
vector<string> generateParenthesis(int n) {
if(n==0) return vector<string>(1,"");
if(n==0) return vector<string>(1,"()");
vector<string> ans;
for(int i=0;i<n;i++)
for(auto inner:generateParenthesis(i))
for(auto outer:generateParenthesis(n-i-1))
ans.push_back("(" + inner +")" + outer);
return ans;
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
