IVYEVIE - EDITORIAL

editorial
, ,
1

PROBLEM LINK:

Practice

Div-2 Contest

Author: Venkatesh G Dhongadi
Tester: Venkatesh G Dhongadi
Editorialist: Venkatesh G Dhongadi

DIFFICULTY:

Easy-Medium

PROBLEM:

You are given X pairs of paranthesis. Generate all possible unique combinations of balanced parantheses of length 2 X . After you do that output them in lexicographically sorted order.

Balanced parentheses means that each opening symbol has a corresponding closing symbol and the pairs of parentheses are properly nested.

PREREQUISITES:

  1. Balance validation
  2. Number of balanced sequences
  3. Formula
  4. Dynamic programming
  5. Finding the lexicographical next balanced sequence

QUICK EXPLANATION:

This problem can be solved using simple recursion by keeping a track of the open and closed brackets that we have put in the string.

EXPLANATION:

We just need to ensure that the we use n open brackets and n closed brackets for building the string and at any instant the number of open brackets inserted are always greater than or equal to the number of closed brackets to ensure that the brackets are balanced.The following logic is implemented in the given code.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;
clock_t time_p = clock();
void time()
{
    time_p = clock() - time_p;
    cerr << "Time elapsed : " << (double)(time_p) / CLOCKS_PER_SEC << '\n';
}
void recur(vector<string>&res, int current_sum, int open, int close, string s)
{
    if (open == 0 and close == 0 and current_sum == 0)
    {
        res.emplace_back(s);
        return;
    }
    if (open > 0)
        recur(res, current_sum + 1, open - 1, close, s + '(');
    if (close > 0 and current_sum > 0)
        recur(res, current_sum - 1, open, close - 1, s + ')');
}
signed main()
{
    int n;
    cin >> n;
    vector<string>res;
    recur(res, 0, n, n, "");
    cout << (int)res.size() << '\n';
    for (auto &x : res)
        cout << x << '\n';
    time();
    return 0;
}
2

At least editorialists should know how to format their code before posting :slight_smile: .