给出一个正整数n,请给出所有的包含n个'('和n个')'的字符串,使得'('和')'可以完全匹配。
例如:
'(())()','()()()' 都是合法的;
'())()('是不合法的。
请按照__字典序__给出所有合法的字符串。
/**
* 寻找合法字符串
* 给出一个正整数n,请给出所有的包含n个'('和n个')'的字符串,使得'('和')'可以完全匹配。
* 例如:
* '(())()','()()()' 都是合法的;
* '())()('是不合法的。
* 请按照__字典序__给出所有合法的字符串。
* 输入描述:
* 输入为1个正整数
* 输出描述:
* 输出为所有合法的字符串,用英文逗号隔开
* 输入例子1:
* 2
* 输出例子1:
* (()),()()
*
* @author shijiacheng
*/
public class FindLegalString {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<String> result = new ArrayList<>();
printHelper(n, n, "", result);
Collections.sort(result);
for (int i = 0; i < result.size(); i++) {
if (i < result.size() - 1) {
System.out.print(result.get(i) + ",");
} else {
System.out.print(result.get(i));
}
}
}
private static void printHelper(int left, int right
, String out, List<String> result) {
if (left < 0 || right < 0 || left > right) {
return;
}
if (left == 0 && right == 0) {
result.add(out);
return;
}
printHelper(left - 1, right, out + "(", result);
printHelper(left, right - 1, out + ")", result);
}
}
#include <iostream> #include <vector> #include <string> using namespace std; // 例子: n = 4 // 先添加左括号: str = "" -> str = "((((" -> str = "(((())))" // str = "" -> str = "((((" -> str = "(((" -> "((()" ... void process(string & str, vector<string> & res, int nl, int nr, int n) { // 若str中左括号的数量和右括号的数量都为n, 则将str添加到结果数组中, 并返回 if (nl >= n && nr >= n) { res.push_back(str); return; } // 原则是先添加左括号 if (nl < n) { // 左括号的数量不超过n str.push_back('('); // 注意process每次都添加扩好并删除括号, 返回时对传入的str没有做改变 process(str, res, nl + 1, nr, n); str.pop_back(); // 删除push_back添加的左括号 } // 若左括号的数量比右括号的多 if (nl > nr) { str.push_back(')'); // 补充一个右括号 process(str, res, nl, nr + 1, n); str.pop_back(); } } int main() { int n = 0; while (cin >> n) { string str; vector<string> res; process(str, res, 0, 0, n); cout << res.front(); for (int i = 1; i < res.size(); ++i) { cout << "," << res[i]; } cout << endl; } return 0; }
var n = parseInt(line); console.log([...new Set(makeString(n))].sort().join(',')); function makeString(n) { if (n == 0) { return ['']; } var arr = makeString(n - 1), len = arr.length, result = []; for(var i = 0; i < len; i++) { let s1 = '()' + arr[i]; result.push(s1); if (arr[i].indexOf('(') > -1) { let tmp = arr[i].split(''); tmp.forEach((item, index) => { if (item == '(') { let s2 = '(' + tmp.slice(0, index + 1).join('') + ')' + tmp.slice(index + 1).join(''); result.push(s2); } }); } let s3 = arr[i] + '()'; result.push(s3); } return result; }
def generate(n): res= [] def dfs(cur_str,left,right,n): if left == n and right == n: res.append(cur_str) if left<right: return if left<n: dfs(cur_str+'(',left+1,right,n) if right<n: dfs(cur_str+')',left,right+1,n) dfs('',0,0,n) return res n = int(input()) res = generate(n) print(','.join(res))
bool isLegal(string s) { int n = s.size(); int sum = 0; for (int i = 0; i < n; ++i) { sum += s[i] == '('? 1 : -1; if (sum < 0)return false; } return true; } void generate(int n){ string s = string(n,'(') + string(n,')'); if(n > 1){ n *= 2; string s1(n,'('); for (int i = 1; i < n; i+=2)s1[i] = ')'; do{ if(isLegal(s))cout << s << ','; next_permutation(s.begin()+1, s.end()-1); }while (s != s1); } cout << s << '\n'; }
var n = Number(readline()); var x = n,y = n; var result = []; var str = ""; var flag = true; combine(str,x,y); function combine(str,x,y){ if (x <= y) { flag = true; } else { flag = false; } if (x == 0 && y == 0 && flag) { result.push(str); return; } else if (x == 0 && y == 0){ return; } if (flag && x >= 0 && y >= 0) { combine(str+'(',x-1,y); combine(str+')',x,y-1); } } print(result.join())
#include <iostream> #include<algorithm> #include <string> #include <vector> using namespace std; void fun(int n, vector<string> &res, string out, int left, int right) { //left目前已经用的左括号的数目,right目前已经用的右括号的数目 if (left == n && right == n) { res.push_back(out); return; } if (left < n) fun(n, res, out + '(', left + 1, right); if (right < left) fun(n, res, out + ')', left, right + 1); } int main() { int n; cin >> n; vector<string> res; fun(n, res, "", 0, 0); cout << res.front(); for (int i = 1; i < res.size(); i++) { cout << "," << res[i]; } cout << endl; system("pause"); return 0; }
// 深度优先搜索#include<iostream>#include<string>#include<vector>using namespace std;string l = "(";string r = ")";vector<string> res;void dfs(string str, int n, int zero, int one){if (zero==n && one==n){res.push_back(str);return;}string str0 = str + l;string str1 = str + r;if(zero==n && one<n) dfs(str1,n,zero,one+1);else{if(zero>=one) {dfs(str0,n,zero+1,one);dfs(str1,n,zero,one+1);}}}int main(){int n;cin >> n;string init = "";dfs(init, n, 0, 0);for(inti=0;i<res.size()-1;i++){cout << res[i] << ",";}cout << res[res.size()-1];}
c=[]
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
vector<string> solve(int n) {
if (n == 0)return {};
vector<vector<string>> all(n+1);
vector<int> nosplit_flag;//标记all[i]中 ,能否左右分割的位置
all[0].push_back("");
nosplit_flag.push_back(-1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < all[i - 1].size(); j++) {//( all[i-1] )
all[i].push_back("(" + all[i - 1][j] + ")");//( all[i-1] ) ,无法左右分割
}
nosplit_flag.push_back(all[i - 1].size());
for (int j = 1; j < i; j++) {
/*
可且仅可分割成两部分 ()all[i-1],(())all[i-2],((()))all[i-3],(()()) all[i-3]...
all_together前组合
*/
for (int k = 0; k < nosplit_flag[j]; k++) {
for (int l = 0; l < all[i - j].size(); l++) {
all[i].push_back(all[j][k] + all[i - j][l]);//((()))all[i-3],(()()) all[i-3]
}
}
}
}
sort(all[n].begin(), all[n].end());
all[n].erase(unique(all[n].begin(), all[n].end()), all[n].end());
return all[n];
}
vector<string> core(int n) {
vector<string> res;
string temp = "";
if (n == 1) {
res.push_back("()");
return res;
}
vector<string> sub = core(n - 1);
for (int i = 0; i < sub.size(); i++) {
string ans1 = "()" + sub[i];
string ans2 = sub[i] + "()";
string ans3 = "(" + sub[i] + ")";
res.push_back(ans3);
res.push_back(ans1);
if (ans1 != ans2) {
res.push_back(ans2);
}
}
return res;
}
};
int main() {
Solution a;
int x;
while (cin >> x) {
int i;
auto res = a.solve(x);
for (i = 0; i <res.size()-1; i++)
cout <<res[i] << ",";
cout << res[i];
}
return 0;
}