Generate Parenthesis

From the start of this blog website, I always wanted to post weekly about the algorithms I solved. Today could mark that day... we'll see.

Stack DSA

The Stack is a data structure that resembles the actual structure of the RAM inside the computer. Items can only be added on top and can be received by popping from the top.
This structure makes this DS suitable for solving problems, including branching and deciding on the latest computed data.

Such as today's question GenerateParanthesis.

`GenerateParanthesis`

The question is, given an integer n. Return all well-formed parentheses strings that you can generate with n pairs of parentheses.

Example 1:

Input: n = 1

Output: ["()"]

Example 2:

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

If you look closely you can see that at most, n number of the same parentheses can be stacked and the opposite kind of parentheses must follow that.

In order to track this we can initialize two integers for the number of open parentheses and closed parentheses, that way we can track and compare them at any time in the code and decide the next parentheses to be added.

There is another side to this question, branching decisions. Since we need to deliver the final result of possible combinations of well-formed parentheses in a List of strings, we can recurse to generate it as it will execute in a stack
like manner it will generate the parentheses by coming back to the latest currPattern and constructing another variation.

public static List<string> GenerateParenthesis(int n)

{

//1 <= n <= 7

//At most, n number of same parantheses can be stacked

//if n is 3 "(((.." and the rest is the close parantheses

//According to that

List<string> result = new();

Construct(n, 0, 0, "", result);

return result;

static void Construct(int n, int openParen, int closeParen, string currPattern, List<string> result)

{

//Base condition for recursion

//as there should be n number of coherent parantheses

if (openParen == n && openParen == closeParen)

{

result.Add(currPattern);

return;

}

//If we have less then required amount of parantheses

if (openParen < n)

Construct(n, openParen + 1, closeParen, currPattern + '(', result);

if (closeParen < openParen)

Construct(n, openParen, closeParen + 1, currPattern + ')', result);

}