Algorithm-Detailed Analysis-Solving a Leetcode Problem (Generate Parenthesis)
Tags: leetcode, csharp, algorithms, tutorial
Published: 2023-12-17 02:30:11

 Solving LeetCode problems is a highly beneficial practice for individuals seeking to enhance their programming skills. It offers a diverse array of algorithmic challenges, fostering proficiency in data structures and efficient problem-solving. Regular engagement sharpens coding skills, instills best practices, and cultivates a systematic and creative approach to complex issues. LeetCode's relevance extends to interview preparation, providing a simulated environment for technical interviews in many technology companies. The platform accommodates various programming languages, promoting versatility, and its community engagement facilitates knowledge-sharing and collaborative learning. With continuous updates and competitive programming opportunities, LeetCode serves as a dynamic resource for staying current in algorithms and programming techniques, making it a valuable investment for lifelong learning and professional growth.

We'll delve into the cognitive processes involved in tackling a LeetCode problem by initially defining the problem at hand and subsequently exploring the systematic thought patterns employed in its resolution. This analytical approach, rooted in problem definition and methodical reasoning, forms a foundational framework applicable to problem-solving across diverse contexts, making it a transferable skill set for addressing various challenges.

**Problem - Generate paranthesis**
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
 
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:
Input: n = 1
Output: ["()"]
 
Constraints:
1 <= n <= 8

**Solution**

Understanding the problem

Here we are asked to generate all well-formed parenthesis given n pairs of them. What are the rules of a well-formed parenthesis?

Number of left parentheses = Number of right parentheses = n
The number of left parentheses at any point of generation should always be greater than the number of right parentheses.
For example, ( ) ) - can never be valid since for the second closing parenthesis there is no matching opening one. 

**Brute Force Method
**
 A brute-force way of solving the problem is to generate all permutations of opening and closing parenthesis and then validate each of them and add the valid ones to the output list.

Generating all permutations of 2n( n left parenthesis + n right parenthesis) would be 2^2n, which is of order 2^n which is exponential time complexity.

Can we do better?
 Coming up with a better approach

Every output has 2n characters. Let us assume n= 2, so we have 4 characters in any valid output.
- - - -
Let us try to fill the characters.  Every blank space can have 2 possible characters, '(' or ')'. So if we try those 2 characters in every blank space there will be 2^n possible ways, which is the same as our brute force solution.

Can we reduce this in any way by using the rules of well-formed parenthesis?
Let us try to fill in the first character. Of the two possible ways to fill in the first character, which one is valid?
 
The only valid character that can go in the first space is a left parenthesis. Having a right parenthesis without a left one makes it invalid. So there is only one possible way to fill in the first space.

Now consider the second space, it can be filled in 2 ways, '(' or ')' because both are valid parenthesis formations. Now we have 2 below states to get to our result list.

( ( - -
( ) - -

Let's consider ( ( - - and try to fill in the third space. Can it have 2 ways of filling in the character? Definitely not. Why? Refer to the Rules of well-formed parenthesis. Since we cannot have more than 2 left parentheses for n =2, only ')' is a valid choice. So now we have 
( ( ) -

Now let's consider ( ), what are the possible choices? Again referring to the rules,
only the left parenthesis is valid since as per the rules number of left parenthesis should always be greater than or equal to the right parenthesis. So our only choice here is ')'

( ) ( -

Now to fill in the last character for both of the above partial results,

( ( ) - and ( ) ( -

Obviously, if we follow the rules we can fill in the partial results to

( ( ) ) and ( ) ( ), which form the output result.

We have reduced the time from generating 2^n results down to a much lesser value. 

Translating the idea into an algorithm - Recursion with backtracking

Now comes the best and the most important part. Translating this idea that we developed above to an algorithm using the concepts and techniques we already know.

So at each step, we want to create a partial solution adding all the possible values for the value to be filled. 

A recursive approach would be a clean way to implement this,

The parameters of the function would be 
 n, which is the input given to the function
 the partial solution that is generated so far
 Collection of results which collects all the fully generated solution
 left that holds the number of left parentheses and
 right parenthesis in the partial solution respectively


**Psuedo Code**

function GenerateParenthasis(n, left, right, partial, final)
   if left == n and right == n
 	copy partial solution to final
  else
    if left < n:
        add '(' to partial
        GenerateParenthesis (n, left+1, right, partial, final)
        remove '(' from partial
    if right < left:
        add ")" to partial
        GenerateParenthesis(n, left, right+1,partial, final)
        remove ')' from partial
end function


**C# implementation**

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2bpnzvyhsbjk3vn3g6a3.png)

We can rewrite the above recursive function in a way that backtracking code comes at the beginning of the code so that it is more evident. Refer to the below code

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cjwkfn1wgavmpnfwb1cm.png)

**Time and Space Complexity**

Time Complexity: nth Catalan number which is 4^n/ Squareroot(n)
Space Complexity: nth Catalan number, 4^n/ Squareroot(n)
        Time and Space complexity have considerably decreased from exponential since we are not proceeding further with the cases where we know it is not going to yield any valid result.  The time complexity corresponds to nth Catalan number, the derivation of which is beyond scope of this. I will have a detailed explanation of it in another post.