Рубрики

Распечатать все комбинации сбалансированных скобок

Напишите функцию для генерации всех возможных n пар сбалансированных скобок.

Примеры:

Input : n=1
Output: {}

Input : n=2
Output: 
{}{}
{{}}

Алгоритм:
Следите за количеством открытых и закрытых скобок.

  1. Инициализируйте эти числа как 0.
  2. Рекурсивно вызывайте функцию _printParenthesis (), пока число открытых скобок не станет меньше заданного n.
    • Если число открытых скобок становится больше, чем количество закрывающих скобок, то установите закрывающую скобку и рекурсивно вызовите оставшиеся скобки.
    • Если число открытых скобок меньше n, тогда поместите открывающую скобку и вызовите _printParenthesis () для оставшихся скобок.

Спасибо Шеху за предоставленный код.

C / C ++

// C программа для печати всех комбинаций
// сбалансированных скобок
# include<stdio.h>
# define MAX_SIZE 100

  

void _printParenthesis(int pos, int n, int open, int close);

  
// Обертка над _printParenthesis ()

void printParenthesis(int n)

{

    if(n > 0)

        _printParenthesis(0, n, 0, 0);

    return;

}     

  

void _printParenthesis(int pos, int n, int open, int close)

{

    static char str[MAX_SIZE];     

      

    if(close == n) 

    {

        printf("%s \n", str);

        return;

    }

    else

    {

        if(open > close) 

        {

            str[pos] = '}';

            _printParenthesis(pos+1, n, open, close+1);

        }

          

        if(open < n)

        {

        str[pos] = '{';

        _printParenthesis(pos+1, n, open+1, close);

        }

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int n = 3;

    printParenthesis(n);

    getchar();

    return 0;

}

Джава

// Java программа для печати всех
// комбинации сбалансированных скобок

import java.io.*;

  

class GFG 

{

    // Функция, которая печатает все комбинации

    // сбалансированные скобки

    // открыть магазин счетчика открывающих скобок

    // закрываем сохраняем количество закрывающих скобок

    static void _printParenthesis(char str[], int pos, int n, int open, int close)

    {

        if(close == n) 

        {

            // выводим возможные комбинации

            for(int i=0;i<str.length;i++)

                System.out.print(str[i]);

            System.out.println();

            return;

        }

        else

        {

            if(open > close) {

                str[pos] = '}';

                _printParenthesis(str, pos+1, n, open, close+1);

            }

            if(open < n) {

                str[pos] = '{';

                _printParenthesis(str, pos+1, n, open+1, close);

            }

        }

    }

      

    // Обертка над _printParenthesis ()

    static void printParenthesis(char str[], int n)

    {

        if(n > 0)

        _printParenthesis(str, 0, n, 0, 0);

        return;

    }

      

    // драйверная программа

    public static void main (String[] args) 

    {

        int n = 3;

        char[] str = new char[2 * n];

        printParenthesis(str, n);

    }

}

  
// Предоставлено Прамод Кумар

python3

# Python3 программа для
# Распечатать все комбинации
Количество сбалансированных скобок

  
# Обертка над _printParenthesis ()

def printParenthesis(str, n):

    if(n > 0):

        _printParenthesis(str, 0

                          n, 0, 0);

    return;

  

def _printParenthesis(str, pos, n, 

                      open, close):

      

    if(close == n):

        for i in str:

            print(i, end = "");

        print();

        return;

    else:

        if(open > close):

            str[pos] = '}';

            _printParenthesis(str, pos + 1, n, 

                              open, close + 1);

        if(open < n):

            str[pos] = '{';

            _printParenthesis(str, pos + 1, n, 

                              open + 1, close);

  
Код водителя

n = 3;

str = [""] * 2 * n;

printParenthesis(str, n);

  
# Этот код добавлен
# Митс.

C #

// C # программа для печати всех
// комбинации сбалансированных скобок

using System;

  

class GFG

{

    // Функция, которая печатает все комбинации

    // сбалансированные скобки

    // открыть магазин счетчика открывающих скобок

    // закрываем сохраняем количество закрывающих скобок

    static void _printParenthesis(char []str,

            int pos, int n, int open, int close)

    {

        if (close == n) 

        {

            // выводим возможные комбинации

            for (int i = 0; i < str.Length; i++)

                Console.Write(str[i]);

              

            Console.WriteLine();

            return;

        }

        else

        {

            if (open > close) {

                str[pos] = '}';

                _printParenthesis(str, pos + 1,

                                n, open, close + 1);

            }

            if (open < n) {

                str[pos] = '{';

                _printParenthesis(str, pos + 1,

                                n, open + 1, close);

            }

        }

    }

      

    // Обертка над _printParenthesis ()

    static void printParenthesis(char []str, int n)

    {

        if(n > 0)

        _printParenthesis(str, 0, n, 0, 0);

        return;

    }

      

    // драйверная программа

    public static void Main() 

    {

        int n = 3;

        char[] str = new char[2 * n];

          

        printParenthesis(str, n);

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для печати
// все комбинации
// сбалансированные скобки

$MAX_SIZE = 100;

  
// Обертка над
// _printParenthesis ()

function printParenthesis($str, $n)

{

    if($n > 0)

        _printParenthesis($str, 0, 

                          $n, 0, 0);

    return;

  
// Функция, которая печатает
// все комбинации

    // сбалансированные скобки

    // открыть магазин

    // открывающая скобка

    // закрываем счетчик

    // закрывающая скобка

function _printParenthesis($str, $pos, $n

                           $open, $close)

{

    if($close == $n

    {

        for ($i = 0; 

             $i < strlen($str); $i++)

        echo $str[$i];

        echo "\n";

        return;

    }

    else

    {

        if($open > $close

        {

            $str[$pos] = '}';

            _printParenthesis($str, $pos + 1, $n,

                              $open, $close + 1);

        }

          

        if($open < $n)

        {

        $str[$pos] = '{';

        _printParenthesis($str, $pos + 1, $n

                          $open + 1, $close);

        }

    }

}

  
// Код драйвера

$n = 3;

$str="     ";

printParenthesis($str, $n);

  
// Этот код предоставлен mits.
?>


Выход:

{}{}{}
{}{{}}
{{}}{}
{{}{}}
{{{}}}

Пожалуйста, пишите комментарии, если вы обнаружите, что вышеприведенные коды / алгоритмы неверны, или найдете лучшие способы решения той же проблемы.

Рекомендуемые посты:

Распечатать все комбинации сбалансированных скобок

0.00 (0%) 0 votes