Поиск всех комбинаций правильных скобок

Question

Это возникло во время разговора с другом, и я подумал, что спрошу здесь, потому что это интересная проблема и хотел бы увидеть решения других людей.

Задача состоит в том, чтобы написать функцию Brackets (int n), которая печатает все комбинации правильно сформированных скобок от 1 ... n. Для скобок (3) вывод будет

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

Answer 1

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 2

Еще один неэффективный, но элегантный ответ =>

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 3

Попытка с памяткой:

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

  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 6

ruby ​​версия:

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 7

//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 8

Не самое элегантное решение, но именно так я и сделал в 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;
}