Solve Leetcode Problems and Get Offers From Your Dream Companies || Generate Parentheses

Question number 22. Generate Parentheses

In this series, I am going to solve Leetcode medium problems live with my friends, which you can see on our youtube channel, Today we will do Problem Problem 22. Generate Parentheses.

A little bit about me, I have offers from Uber India and Amazon India in the past, and I am currently working for Booking.com in Amsterdam.

Motivation to learn algorithms

Problem Statement:

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

Youtube Discussion

Solution

This is a backtracking problem. We have to generate all valid combinations of parentheses. First, we must identify what are the characteristics of a valid string. Their length should be 2*n, where n is the given number. Also, the order of the parenthesis is also important. We can only put opening parenthesis first and the no of opening and closing parenthesis should be same. Therefore we need to keep track of opening and closing parenthesis too.

Therefore at first, we called the solve method with left and right value as 0 and empty string. We add an opening string to the string and call this method again with modified parameters. If it is not possible to add an opening parenthesis, we add one closing parenthesis and backtrack again. When we find the length of the string as 2*n we add that string to our global list. This can be understood with the dry run given in the code.

The following is the Java code for this problem.

The C++ code is given below.

The code can be found in this repository.

Sign up for Leetcode Simplified
By LeetCode Simplified

Get latest leetcode solution with youtube breakdown Take a look
You're an editor of Leetcode Simplified