1.题目描述
给出一个正整数 n，请给出所有的包含 n 个'('和 n 个')'的字符串，使得'('和')'可以完全匹配。
- 例如：
'(())()'，'()()()' 都是合法的；
'())()('是不合法的。
请按照字典序给出所有合法的字符串。
- 输入描述:
输入为 1 个正整数 - 输出描述:
输出为所有合法的字符串，用英文逗号隔开 - 输入示例：
2 - 输出示例：
(()),()()
2.题目解析
3.参考答案
方法一：
构造字符串，并且将字符串排列组合，过滤掉不匹配的情况，保留剩下的即为结果。
#include <bits/stdc++.h>
using namespace std;
bool check(string s){
vector<char> stack;
for(int i=0;i<s.size();++i){
if(s[i] == '('){
stack.push_back('(');
}else if(s[i] == ')'){
if(stack.empty()){// 如果前面没有做左括号，不匹配
return false;
}
stack.pop_back();
}
}
return stack.empty();
}
int main() {
int n;
scanf("%d",&n);
string s = string(n,'(')+string(n,')');
set<string> res;
res.insert(s);
do {
if(check(s)){
res.insert(s);
}
} while(next_permutation(s.begin(), s.end()));
bool start = true;
for(string str:res){
if(start)start = false; // 除去开头，
else cout <<',';
cout << str ;
}
cout << '\n';
}
方法二：回溯法
回溯法的前提是熟练掌握和理解递归。
#include <bits/stdc++.h>
using namespace std;
void solve(int left, int right, string str, vector<string>& res){
if (left == 0 && right == 0){
res.push_back(str);
return;
}
if (left>0) solve(left - 1, right, str + '(', res);
if (right>left) solve(left, right - 1, str + ')', res);
}
int main(){
int n;
scanf("%d",&n);
vector<string> res;
solve(n,n,"",res);
// 打印结果
for(int i=0;i!=res.size();++i){
cout << res[i];
if(i!=res.size()-1){
cout << ",";
}
}
cout << endl;
return 0;
}
解析
- 当
n=2时
solve(2,2,"")
solve(1,2,"(")
solve(0,2,"((")
solve(0,1,"(()")
solve(0,0,"(())")
solve(1,1,"()")
solve(0,1,"()(")
solve(0,0,"()()")
- 当
n=3时
solve(3,3,"")
solve(2,3,"(")
solve(1,3,"((")
solve(0,3,"(((")
solve(0,2,"((()")
solve(0,1,"((())")
solve(0,0,"((()))")
solve(1,2,"(()")
solve(0,2,"(()(")
solve(0,1,"(()()")
solve(0,0,"(()())")
solve(1,1,"(())")
solve(0,1,"(())(")
solve(0,0,"(())()")
solve(2,2,"()")
solve(1,2,"()(")
solve(0,2,"()((")
solve(0,1,"()(()")
solve(0,0,"()(())")
solve(1,1,"()()")
solve(0,1,"()()(")
solve(0,0,"()()()")
- 当
n=4时
solve(4,4,"")
solve(3,4,"(")
solve(2,4,"((")
solve(1,4,"(((")
solve(0,4,"((((")
solve(0,3,"(((()")
solve(0,2,"(((())")
solve(0,1,"(((()))")
solve(0,0,"(((())))")
solve(1,3,"((()")
solve(0,3,"((()(")
solve(0,2,"((()()")
solve(0,1,"((()())")
solve(0,0,"((()()))")
solve(1,2,"((())")
solve(0,2,"((())(")
solve(0,1,"((())()")
solve(0,0,"((())())")
solve(1,1,"((()))")
solve(0,1,"((()))(")
solve(0,0,"((()))()")
solve(2,3,"(()")
solve(1,3,"(()(")
solve(0,3,"(()((")
solve(0,2,"(()(()")
solve(0,1,"(()(())")
solve(0,0,"(()(()))")
solve(1,2,"(()()")
solve(0,2,"(()()(")
solve(0,1,"(()()()")
solve(0,0,"(()()())")
solve(1,1,"(()())")
solve(0,1,"(()())(")
solve(0,0,"(()())()")
solve(2,2,"(())")
solve(1,2,"(())(")
solve(0,2,"(())((")
solve(0,1,"(())(()")
solve(0,0,"(())(())")
solve(1,1,"(())()")
solve(0,1,"(())()(")
solve(0,0,"(())()()")
solve(3,3,"()")
solve(2,3,"()(")
solve(1,3,"()((")
solve(0,3,"()(((")
solve(0,2,"()((()")
solve(0,1,"()((())")
solve(0,0,"()((()))")
solve(1,2,"()(()")
solve(0,2,"()(()(")
solve(0,1,"()(()()")
solve(0,0,"()(()())")
solve(1,1,"()(())")
solve(0,1,"()(())(")
solve(0,0,"()(())()")
solve(2,2,"()()")
solve(1,2,"()()(")
solve(0,2,"()()((")
solve(0,1,"()()(()")
solve(0,0,"()()(())")
solve(1,1,"()()()")
solve(0,1,"()()()(")
solve(0,0,"()()()()")
