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

Solve Leetcode Problems and Get Offers From Your Dream Companies | by Nil Madhab | LeetCode Simplified | Medium

Nil Madhab ・ Feb 6, 2021 ・

Medium

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.

	public class LC22 {
	// solve called for : left : 0 right : 0
	// solve called for : ( left : 1 right : 0
	// solve called for : (( left : 2 right : 0
	// solve called for : ((( left : 3 right : 0
	// solve called for : ((() left : 3 right : 1
	// solve called for : ((()) left : 3 right : 2
	// solve called for : ((())) left : 3 right : 3
	// solve called for : (() left : 2 right : 1
	// solve called for : (()( left : 3 right : 1
	// solve called for : (()() left : 3 right : 2
	// solve called for : (()()) left : 3 right : 3
	// solve called for : (()) left : 2 right : 2
	// solve called for : (())( left : 3 right : 2
	// solve called for : (())() left : 3 right : 3
	// solve called for : () left : 1 right : 1
	// solve called for : ()( left : 2 right : 1
	// solve called for : ()(( left : 3 right : 1
	// solve called for : ()(() left : 3 right : 2
	// solve called for : ()(()) left : 3 right : 3
	// solve called for : ()() left : 2 right : 2
	// solve called for : ()()( left : 3 right : 2
	// solve called for : ()()() left : 3 right : 3
	// answer -> ((())) (()()) (())() ()(()) ()()()
	static List<String> ans;
	public static void main(String[] args) {
	generateParenthesis(3);
	for (String c:ans)
	System.out.print(c + " ");
	}
	public static List<String> generateParenthesis(int n) {
	ans = new ArrayList<>();
	solve("",0,0,n);
	return ans;
	}
	private static void solve(String str,int left,int right,int n){
	System.out.println("solve called for : " + str + " left : " + left + " right : " + right);
	if(str.length()==2*n)
	ans.add(str);
	if(left<n){
	String temp1 = str;
	temp1+="(";
	solve(temp1,left+1,right,n);
	}
	if(right<left){
	String temp1 = str;
	temp1 += ")";
	solve(temp1,left,right+1,n);
	}
	}
	}

view raw LC22.java hosted with ❤ by GitHub

The C++ code is given below.

	class LC22 {
	public:
	vector<string> generateParenthesis(int n) {
	vector<string> parens;
	string paren;
	generate(n, 0, 0, paren, parens);
	return parens;
	}
	private:
	void generate(int n, int l, int r, string paren, vector<string>& parens) {
	if (l == n && r == n) {
	parens.push_back(paren);
	} else {
	if (l < n) {
	generate(n, l + 1, r, paren + '(', parens);
	}
	if (r < l) {
	generate(n, l, r + 1, paren + ')', parens);
	}
	}
	}
	};

view raw LC22.cpp hosted with ❤ by GitHub

The code can be found in this repository.

webtutsplus / LeetCode

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