这是在与朋友交谈时出现的，我想我会在这里问，因为这是一个有趣的问题，并且希望看到其他人的解决方案。
任务是编写一个函数 Brackets(int n) 打印从 1...n 开始的所有格式正确的括号组合。对于括号（3），输出将是
()
(()) ()()
((())) (()()) (())() ()(()) ()()()
问问题
24909 次
29 回答
54
对它进行了破解.. C# 也是。
public void Brackets(int n) {
for (int i = 1; i <= n; i++) {
Brackets("", 0, 0, i);
}
}
private void Brackets(string output, int open, int close, int pairs) {
if((open==pairs)&&(close==pairs)) {
Console.WriteLine(output);
} else {
if(open<pairs)
Brackets(output + "(", open+1, close, pairs);
if(close<open)
Brackets(output + ")", open, close+1, pairs);
}
}
递归利用了这样一个事实，即您永远不能添加比所需对数更多的左括号，并且您永远不能添加比左括号更多的右括号。
于 2009-04-08T00:03:50.260 回答
10
Python 版本的第一个投票答案。
def foo(output, open, close, pairs):
if open == pairs and close == pairs:
print output
else:
if open<pairs:
foo(output+'(', open+1, close, pairs)
if close<open:
foo(output+')', open, close+1, pairs)
foo('', 0, 0, 3)
于 2012-11-21T13:22:57.870 回答
9
F#：
这是一个解决方案，与我之前的解决方案不同，我相信它可能是正确的。此外，它更有效。
#light
let brackets2 n =
let result = new System.Collections.Generic.List<_>()
let a = Array.create (n*2) '_'
let rec helper l r diff i =
if l=0 && r=0 then
result.Add(new string(a))
else
if l > 0 then
a.[i] <- '('
helper (l-1) r (diff+1) (i+1)
if diff > 0 then
a.[i] <- ')'
helper l (r-1) (diff-1) (i+1)
helper n n 0 0
result
例子：
(brackets2 4) |> Seq.iter (printfn "%s")
(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)
于 2009-04-07T22:52:21.070 回答
9
可能组合的数量是 N 对 C(n)的加泰罗尼亚数。
这个问题在 joelonsoftware.com 论坛上进行了相当广泛的讨论，包括迭代、递归和迭代/位移解决方案。那里有一些很酷的东西。
这是 C# 论坛上建议的快速递归解决方案：
C＃
public void Brackets(int pairs) {
if (pairs > 1) Brackets(pairs - 1);
char[] output = new char[2 * pairs];
output[0] = '(';
output[1] = ')';
foo(output, 1, pairs - 1, pairs, pairs);
Console.writeLine();
}
public void foo(char[] output, int index, int open, int close,
int pairs) {
int i;
if (index == 2 * pairs) {
for (i = 0; i < 2 * pairs; i++)
Console.write(output[i]);
Console.write('\n');
return;
}
if (open != 0) {
output[index] = '(';
foo(output, index + 1, open - 1, close, pairs);
}
if ((close != 0) && (pairs - close + 1 <= pairs - open)) {
output[index] = ')';
foo(output, index + 1, open, close - 1, pairs);
}
return;
}
括号（3）；
输出：
()
(()) ()()
((())) (()()) (())() ()(()) ()()()
于 2009-04-07T23:14:15.073 回答
5
这是另一个 F# 解决方案，它更注重优雅而不是效率，尽管记忆化可能会导致性能相对较好的变体。
let rec parens = function
| 0 -> [""]
| n -> [for k in 0 .. n-1 do
for p1 in parens k do
for p2 in parens (n-k-1) ->
sprintf "(%s)%s" p1 p2]
同样，这只会产生一个包含恰好n 对括号（而不是最多 n）的字符串列表，但很容易包装它。
于 2009-04-08T03:26:35.607 回答
4
F#：
更新：这个答案是错误的。我的 N=4 未命中，例如“(())(())”。（你明白为什么吗？）我很快就会发布一个正确的（更有效的）算法。
（对所有支持投票的人感到羞耻，因为没有抓住我！:)）
效率低下，但简短而简单。（请注意，它只打印“第 n”行；从 1..n 循环调用以获取问题所要求的输出。）
#light
let rec brackets n =
if n = 1 then
["()"]
else
[for s in brackets (n-1) do
yield "()" ^ s
yield "(" ^ s ^ ")"
yield s ^ "()"]
例子：
Set.of_list (brackets 4) |> Set.iter (printfn "%s")
(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)
于 2009-04-07T21:55:26.667 回答
4
C++ 中的简单解决方案：
#include <iostream>
#include <string>
void brackets(string output, int open, int close, int pairs)
{
if(open == pairs && close == pairs)
cout << output << endl;
else
{
if(open<pairs)
brackets(output+"(",open+1,close,pairs);
if(close<open)
brackets(output+")",open,close+1,pairs);
}
}
int main()
{
for(int i=1;i<=3;i++)
{
cout << "Combination for i = " << i << endl;
brackets("",0,0,i);
}
}
输出：
Combination for i = 1
()
Combination for i = 2
(())
()()
Combination for i = 3
((()))
(()())
(())()
()(())
()()()
于 2010-08-05T21:31:52.087 回答
3
该死-每个人都击败了我，但我有一个很好的工作示例:)
http://www.fiveminuteargument.com/so-727707
关键是确定规则，这实际上非常简单：
- 逐个字符地构建字符串
- 在字符串中的给定点
- 如果到目前为止字符串中的括号平衡（包括空str），则添加一个左括号并递归
- 如果已使用所有开括号，则添加右括号并递归
- 否则，递归两次，每种类型的括号一次
- 当你到达终点时停止:-)
于 2009-04-07T23:44:26.577 回答
3
普通 Lisp：
这不会打印它们，但会生成所有可能结构的列表。我的方法和其他人有点不同。它将解决方案重组brackets(n - 1)为brackets(n). 我的解决方案不是尾递归的，但可以通过一些工作来实现。
代码
(defun brackets (n)
(if (= 1 n)
'((()))
(loop for el in (brackets (1- n))
when (cdr el)
collect (cons (list (car el)) (cdr el))
collect (list el)
collect (cons '() el))))
于 2009-04-13T21:17:49.257 回答
2
这是 C++ 中的解决方案。我使用的主要思想是从前一个i获取输出（其中i是括号对的数量），并将其作为输入提供给下一个i。然后，对于输入中的每个字符串，我们在字符串中的每个位置放置一个括号对。将新字符串添加到集合中以消除重复。
#include <iostream>
#include <set>
using namespace std;
void brackets( int n );
void brackets_aux( int x, const set<string>& input_set, set<string>& output_set );
int main() {
int n;
cout << "Enter n: ";
cin >> n;
brackets(n);
return 0;
}
void brackets( int n ) {
set<string>* set1 = new set<string>;
set<string>* set2;
for( int i = 1; i <= n; i++ ) {
set2 = new set<string>;
brackets_aux( i, *set1, *set2 );
delete set1;
set1 = set2;
}
}
void brackets_aux( int x, const set<string>& input_set, set<string>& output_set ) {
// Build set of bracket strings to print
if( x == 1 ) {
output_set.insert( "()" );
}
else {
// For each input string, generate the output strings when inserting a bracket pair
for( set<string>::iterator s = input_set.begin(); s != input_set.end(); s++ ) {
// For each location in the string, insert bracket pair before location if valid
for( unsigned int i = 0; i < s->size(); i++ ) {
string s2 = *s;
s2.insert( i, "()" );
output_set.insert( s2 );
}
output_set.insert( *s + "()" );
}
}
// Print them
for( set<string>::iterator i = output_set.begin(); i != output_set.end(); i++ ) {
cout << *i << " ";
}
cout << endl;
}
于 2009-04-07T23:48:33.463 回答
2
一个简单的 F#/OCaml 解决方案：
let total_bracket n =
let rec aux acc = function
| 0, 0 -> print_string (acc ^ "\n")
| 0, n -> aux (acc ^ ")") (0, n-1)
| n, 0 -> aux (acc ^ "(") (n-1, 1)
| n, c ->
aux (acc ^ "(") (n-1, c+1);
aux (acc ^ ")") (n, c-1)
in
aux "" (n, 0)
于 2009-04-09T22:52:55.190 回答
2
基于递归回溯算法的Provider C#版本，希望对您有所帮助。
public List<String> generateParenthesis(int n) {
List<String> result = new LinkedList<String>();
Generate("", 0, 0, n, result);
return result;
}
private void Generate(String s, int l, int r, int n, List<String> result){
if(l == n && r == n){
result.add(s);
return;
}
if(l<n){
Generate(s+"(", l+1, r, n, result);
}
if(r < l)
Generate(s+")", l , r+1, n, result);
}}
于 2018-02-11T17:34:29.767 回答
1
def @memo brackets ( n )
=> [] if n == 0 else around( n ) ++ pre( n ) ++ post( n ) ++ [ "()" * n) ]
def @memo pre ( n )
=> map ( ( s ) => "()" ++ s, pre ( n - 1 ) ++ around ( n - 1 ) ) if n > 2 else []
def @memo post ( n )
=> map ( ( s ) => s ++ "()", post ( n - 1 ) ++ around ( n - 1 ) ) if n > 2 else []
def @memo around ( n )
=> map ( ( s ) => "(" ++ s ++ ")", brackets( n - 1 ) )
（kin，这有点像基于actor模型的具有特征的线性python。我还没有开始实现@memo，但上面的工作没有优化）
于 2009-04-08T12:56:01.260 回答
1
哈斯克尔：
我试图想出一个优雅的 list monad-y 方法：
import Control.Applicative
brackets :: Int -> [String]
brackets n = f 0 0 where
f pos depth =
if pos < 2*n
then open <|> close
else stop where
-- Add an open bracket if we can
open =
if depth < 2*n - pos
then ('(' :) <$> f (pos+1) (depth+1)
else empty
-- Add a closing bracket if we can
close =
if depth > 0
then (')' :) <$> f (pos+1) (depth-1)
else empty
-- Stop adding text. We have 2*n characters now.
stop = pure ""
main = readLn >>= putStr . unlines . brackets
于 2010-08-06T17:48:40.347 回答
1
为什么不能这么简单，这个想法很简单
括号（n）->'（）'+括号（n-1）0'（'+括号（n-1）+'）'0括号（n-1）+'（）'
其中 0 是上面的串联操作
public static Set<String> brackets(int n) {
if(n == 1){
Set<String> s = new HashSet<String>();
s.add("()");
return s;
}else{
Set<String> s1 = new HashSet<String>();
Set<String> s2 = brackets(n - 1);
for(Iterator<String> it = s2.iterator(); it.hasNext();){
String s = it.next();
s1.add("()" + s);
s1.add("(" + s + ")");
s1.add(s + "()");
}
s2.clear();
s2 = null;
return s1;
}
}
于 2010-08-24T20:58:14.690 回答
1
Groovy 版本基于上面 markt 优雅的 c# 解决方案。动态检查打开和关闭（信息在输出和参数中重复）以及删除一些无关的逻辑检查。
3.times{
println bracks(it + 1)
}
def bracks(pairs, output=""){
def open = output.count('(')
def close = output.count(')')
if (close == pairs) {
print "$output "
}
else {
if (open < pairs) bracks(pairs, "$output(")
if (close < open) bracks(pairs, "$output)")
}
""
}
于 2010-12-11T21:04:56.777 回答
0
不是最优雅的解决方案，但这就是我在 C++ (Visual Studio 2008) 中的做法。利用 STL 集消除重复，我只是天真地将新 () 对插入到上一代的每个字符串的每个字符串索引中，然后递归。
#include "stdafx.h"
#include <iostream>
#include <string>
#include <set>
using namespace System;
using namespace std;
typedef set<string> StrSet;
void ExpandSet( StrSet &Results, int Curr, int Max )
{
if (Curr < Max)
{
StrSet NewResults;
for (StrSet::iterator it = Results.begin(); it != Results.end(); ++it)
{
for (unsigned int stri=0; stri < (*it).length(); stri++)
{
string NewStr( *it );
NewResults.insert( NewStr.insert( stri, string("()") ) );
}
}
ExpandSet( NewResults, Curr+1, Max );
Results = NewResults;
}
}
int main(array<System::String ^> ^args)
{
int ParenCount = 0;
cout << "Enter the parens to balance:" << endl;
cin >> ParenCount;
StrSet Results;
Results.insert( string("()") );
ExpandSet(Results, 1, ParenCount);
cout << Results.size() << ": Total # of results for " << ParenCount << " parens:" << endl;
for (StrSet::iterator it = Results.begin(); it != Results.end(); ++it)
{
cout << *it << endl;
}
return 0;
}
于 2010-06-05T11:10:39.133 回答
0
//C program to print all possible n pairs of balanced parentheses
#include<stdio.h>
void fn(int p,int n,int o,int c);
void main()
{
int n;
printf("\nEnter n:");
scanf("%d",&n);
if(n>0)
fn(0,n,0,0);
}
void fn(int p,int n,into,int c)
{
static char str[100];
if(c==n)
{
printf("%s\n",str);
return;
}
else
{
if(o>c)
{
str[p]='}';
fn(p+1,n,o,c+1);
}
if(o<n)
{
str[p]='{';
fn(p+1,n;o+1,c);
}
}
}
于 2013-09-05T17:41:23.913 回答
0
红宝石版本：
def foo output, open, close, pairs
if open == pairs and close == pairs
p output
else
foo(output + '(', open+1, close, pairs) if open < pairs
foo(output + ')', open, close+1, pairs) if close < open
end
end
foo('', 0, 0, 3)
于 2014-11-06T05:52:46.930 回答
0
validParentheses: function validParentheses(n) {
if(n === 1) {
return ['()'];
}
var prevParentheses = validParentheses(n-1);
var list = {};
prevParentheses.forEach(function(item) {
list['(' + item + ')'] = null;
list['()' + item] = null;
list[item + '()'] = null;
});
return Object.keys(list);
}
于 2015-08-25T09:50:46.027 回答
0
public static void printAllValidBracePermutations(int size) {
printAllValidBracePermutations_internal("", 0, 2 * size);
}
private static void printAllValidBracePermutations_internal(String str, int bal, int len) {
if (len == 0) System.out.println(str);
else if (len > 0) {
if (bal <= len / 2) printAllValidBracePermutations_internal(str + "{", bal + 1, len - 1);
if (bal > 0) printAllValidBracePermutations_internal(str + "}", bal - 1, len - 1);
}
}
于 2015-11-29T18:54:22.763 回答
0
另一个低效但优雅的答案=>
public static Set<String> permuteParenthesis1(int num)
{
Set<String> result=new HashSet<String>();
if(num==0)//base case
{
result.add("");
return result;
}
else
{
Set<String> temp=permuteParenthesis1(num-1); // storing result from previous result.
for(String str : temp)
{
for(int i=0;i<str.length();i++)
{
if(str.charAt(i)=='(')
{
result.add(insertParen(str, i)); // addinng `()` after every left parenthesis.
}
}
result.add("()"+str); // adding "()" to the beginning.
}
}
return result;
}
public static String insertParen(String str,int leftindex)
{
String left=str.substring(0, leftindex+1);
String right=str.substring(leftindex+1);
return left+"()"+right;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(permuteParenthesis1(3));
}
于 2016-02-27T18:44:44.833 回答
0
记忆的尝试：
void push_strings(int i, int j ,vector<vector <string>> &T){
for (int k=0; k< T[j].size(); ++k){
for (int l=0; l< T[i - 1 - j].size(); ++l){
string s = "(" + T[j][k] + ")" + T[i-1 - j][l];
T[i].push_back(s);
}
}
}
vector<string> generateParenthesis(int n) {
vector<vector <string>> T(n+10);
T[0] = {""};
for (int i =1; i <=n; ++i){
for(int j=0; j<i; ++j){
push_strings(i,j, T);
}
}
return T[n];
}
于 2016-03-16T10:46:57.967 回答
0
def form_brackets(n: int) -> set:
combinations = set()
if n == 1:
combinations.add('()')
else:
previous_sets = form_brackets(n - 1)
for previous_set in previous_sets:
for i, c in enumerate(previous_set):
temp_string = "{}(){}".format(previous_set[:i+1], previous_set[i+1:])
combinations.add(temp_string)
return combinations
于 2016-10-09T22:50:49.640 回答
0
void function(int n, string str, int open, int close)
{
if(open>n/2 || close>open)
return;
if(open==close && open+close == n)
{
cout<<" "<<str<<endl;
return;
}
function(n, str+"(", open+1, close);
function(n, str+")", open, close+1);
}
来电者 - function(2*brackets, str, 0, 0);
于 2016-10-24T10:58:02.730 回答
0
我今天接受采访时被问到这个问题。
我在破解编码中总是跳过这个问题，因为我认为这是一个面试的愚蠢问题。不过面试官并没有同意我的看法。
以下是我在面试中可以提出的解决方案。面试官正在研究上面已经给出的更高效的方法。他通过了我这个解决方案。
//This method is recursive. It simply returns all the possible arrangements by going down
//and building all possible combinations of parenthesis arrangements by starting from "()"
//Using only "()" for n == 1, it puts one "()" before, one "()" after and one "()" around
//each paren string returned from the call stack below. Since, we are adding to a set, the
//set ensure that any combination is not repeated.
private HashSet<string> GetParens(int num)
{
//If num < 1, return null.
if (num < 1) return null;
//If num == 1, there is only valid combination. Return that.
if (num == 1) return new HashSet<string> {"()"};
//Calling myself, by subtracting 1 from the input to get valid combinations for 1 less
//pair.
var parensNumMinusOne = GetParens(num - 1);
//Initializing a set which will hold all the valid paren combinations.
var returnSet = new HashSet<string>();
//Now generating combinations by using all n - 1 valid paren combinations one by one.
foreach (var paren in parensNumMinusOne)
{
//Putting "()" before the valid paren string...
returnSet.Add("()" + paren);
//Putting "()" after the valid paren string...
returnSet.Add(paren + "()");
//Putting paren pair around the valid paren string...
returnSet.Add("(" + paren + ")");
}
return returnSet;
}
其他性能更高的解决方案的空间复杂度是 O(1)，但对于这个是 O( C n )，其中C n是Catalan Number。
此代码的时间复杂度与其他高性能解决方案相同，与 O( C n ) 相同。
于 2017-11-25T05:20:21.560 回答
0
在 javascript/nodejs 中。
该程序最初旨在回答终极问题，但枚举有效括号组合非常完美。
function* life(universe){
if( !universe ) yield '';
for( let everything = 1 ; everything <= universe ; ++everything )
for( let meaning of life(everything - 1) )
for( let question of life(universe - everything) )
yield question + '(' + meaning + ')';
}
let love = 5;
let answer = [...life(love)].length;
console.log(answer);
function brackets(n){
for( k = 1 ; k <= n ; k++ ){
console.log(...life(k));
}
}
brackets(5);
于 2020-10-21T20:45:48.870 回答
0
public class Solution {
public IList<string> GenerateParenthesis(int n) {
List<string> combinations = new List<string>();
generateAll(new char[2 * n], 0, combinations);
return combinations;
}
public void generateAll(char[] current, int pos, List<string> result) {
if (pos == current.Length) {
if (valid(current))
result.Add(new string(current));
} else {
current[pos] = '(';
generateAll(current, pos+1, result);
current[pos] = ')';
generateAll(current, pos+1, result);
}
}
public bool valid(char[] current) {
int balance = 0;
foreach (char c in current) {
if (c == '(')
balance++;
else balance--;
if (balance < 0)
return false;
}
return (balance == 0);
}
}
于 2022-01-07T12:10:51.850 回答
-1
在 C# 中
public static void CombiParentheses(int open, int close, StringBuilder str)
{
if (open == 0 && close == 0)
{
Console.WriteLine(str.ToString());
}
if (open > 0) //when you open a new parentheses, then you have to close one parentheses to balance it out.
{
CombiParentheses(open - 1, close + 1, str.Append("{"));
}
if (close > 0)
{
CombiParentheses(open , close - 1, str.Append("}"));
}
}
于 2017-03-13T05:49:58.117 回答