查找格式正确的括号的所有组合

Question

这是在与朋友交谈时提出的，我想我应该在这里问，因为这是一个有趣的问题，并且希望看到其他人的解决方案。

任务是编写一个函数 Brackets(int n)，打印 1...n 中所有格式良好括号的组合。 对于括号（3），输出将是

()
(())  ()()   
((()))  (()())  (())()  ()(())  ()()()

Answer 1

//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);
        }
    }
}

Answer 2

红宝石版本：

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)

Answer 3

  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);
  }

Answer 4

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);
    }
}

Answer 5

另一个低效但优雅的答案=>

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));

}

Answer 6

记忆化的尝试：

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];
}

Answer 7

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

Answer 8

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);

Answer 9

我今天在接受采访时被问到这个问题。

我总是在《破解编码》中跳过这个问题，因为我认为这对于面试来说是一个愚蠢的问题。 但面试官并没有同意我的观点。

以下是我在采访中可能提出的解决方案。 面试官正在寻找上面已经给出的更高效的方法。 但他通过了我的解决方案。

//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 是加泰罗尼亚号码。

该代码的时间复杂度与其他高性能解决方案相同，均为 O(C_n)。

Answer 10

在 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);

Answer 11

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);
    }
}

Answer 12

处理此问题的另一个解决方案。

正确的字符串：(){}[]
字符串不正确：([{)]}

 private static boolean isEqualBracket(String str) {
            Stack stack = new Stack();
            if (str != null && str.length() > 0) {
                for (int i = 0; i < str.length(); i++) {
                    char nextChar = str.charAt(i);
                    if (nextChar == '(' || nextChar == '{' || nextChar == '[') {
                        stack.push(nextChar);
                    } else if (nextChar == ')' || nextChar == '}' || nextChar == ']') {
                        char startChar = stack.peek().toString().charAt(0);
                        if ((startChar == '(' && nextChar == ')') || (startChar == '{' && nextChar == '}') || (startChar == '[' && nextChar == ']')) {
                            stack.pop();
                        } else {
                            return false;
                        }
                    } else {
                        return false;
                    }
                }
            } else {
                return false;
            }
            return stack.empty();
    }

Answer 13

在 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("}"));
        }
    }

Answer 14

尝试了一下..还有 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);
    }
}

递归利用了这样一个事实：添加的左括号永远不能多于所需的对数，并且添加的右括号永远不能多于左括号。

Answer 15

第一个投票答案的 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)

Answer 16

可能组合的数量是 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;
}

Brackets(3)；

输出：
()
(()) ()()
((())) (()()) (())() ()(()) ()()()

Answer 17

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")

(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)

Answer 18

这是另一个 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 个）的字符串列表，但很容易将其包装起来。

Answer 19

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")
(*
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
*)

Answer 20

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
((()))
(()())
(())()
()(())
()()()

Answer 21

该死的 - 每个人都比我先一步，但我有一个很好的工作示例:)

http://www. FiveMinuteargument .com/so-727707

关键是识别规则，实际上非常简单：

• 逐个字符构建字符串
• 在字符串中的给定点
  • 如果到目前为止字符串中的括号平衡（包括空 str），则添加一个左括号并递归
  • 如果所有左括号都已使用，则添加右括号并递归
  • 否则，递归两次，每种括号类型一次
• 停止你就到了最后:-)

Answer 22

Common 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))))

Answer 23

这是 C++ 中的解决方案。 我使用的主要想法是，我获取前一个 i 的输出（其中 i 是括号对的数量），并将其作为输入提供给下一个 < em>我。 然后，对于输入中的每个字符串，我们在字符串中的每个位置放置一个括号对。 将新字符串添加到集合中以消除重复项。

#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;
}

Answer 24

一个简单的 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)

Answer 25

基于递归回溯算法的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);
 }}

Answer 26

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，这类似于具有特征的基于演员模型的线性Python。我没有抽出时间来实现@memo，但上面的方法在没有优化的情况下也能工作）

Answer 27

Haskell：

我试图想出一个优雅的列表单子方式：

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 ('(' :) <
gt; f (pos+1) (depth+1)
                        else empty

                -- Add a closing bracket if we can
                close = 
                    if depth > 0
                        then (')' :) <
gt; f (pos+1) (depth-1)
                        else empty

                -- Stop adding text.  We have 2*n characters now.
                stop = pure ""

main = readLn >>= putStr . unlines . brackets

Answer 28

为什么不能这么简单，这个想法很简单

bracket(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;
    }
}

Answer 29

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)")
    }
    ""
}

Answer 30

这不是最优雅的解决方案，但这就是我在 C++ (Visual Studio 2008) 中的做法。 利用 STL 集来消除重复项，我只是天真地将 new () 对插入到上一代的每个字符串中的每个字符串索引中，然后递归。

#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;
}