Generate All Strings With n Matched Parentheses - Backtracking ("Generate Parentheses" on LeetCode)
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching
Question: Write a program that takes as input a number n in and returns all the strings with n matched pairs of parens.
Examples:
n = 1
[ "()" ]
n = 2
[ "(())", "()()" ]
n = 3
[ "((()))","(()())","(())()","()(())","()()()" ]
Approach 1 (Brute Force Then Validate)
Generate all (2 ^ (2n)) possible parenthese strings and then validate each for being balanced.
If n = 2 then the string length will be 2 times that since all open parentheses are matched by closed parentheses.
This lower bounds our time complexity.
Even if we restrict the enumeration to just sets with an equal number of left and right parentheses we will have choose(2k, k) strings to consider for validation.
Approach 2 (Directed Backtracking)
The 3 Keys To Backtracking
Our Choice:
Whether we place a left or right paren at a certain decision point in our recursion.
Our Constraints:
We can't place a right paren unless we have left parens to match against.
Our Goal:
Place all k left and all k right parens.
The Key
At each point of constructing the string of length 2k we make a choice.
We can place a "(" and recurse or we can place a ")" and recurse.
But we can't just do that placement, we need 2 critical pieces of information.
The amount of left parens left to place.
The amount of right parens left to place.
We have 2 critical rules at each placement step.
We can place a left parentheses if we have more than 0 left to place.
We can only place a right parentheses if there are left parentheses that we can match against.
We know this is the case when we have less left parentheses to place than right parentheses to place.
Once we establish these constraints on our branching we know that when we have 0 of both parens to place that we are done, we have an answer in our base case.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 16.6 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
Видео Generate All Strings With n Matched Parentheses - Backtracking ("Generate Parentheses" on LeetCode) канала Back To Back SWE
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching
Question: Write a program that takes as input a number n in and returns all the strings with n matched pairs of parens.
Examples:
n = 1
[ "()" ]
n = 2
[ "(())", "()()" ]
n = 3
[ "((()))","(()())","(())()","()(())","()()()" ]
Approach 1 (Brute Force Then Validate)
Generate all (2 ^ (2n)) possible parenthese strings and then validate each for being balanced.
If n = 2 then the string length will be 2 times that since all open parentheses are matched by closed parentheses.
This lower bounds our time complexity.
Even if we restrict the enumeration to just sets with an equal number of left and right parentheses we will have choose(2k, k) strings to consider for validation.
Approach 2 (Directed Backtracking)
The 3 Keys To Backtracking
Our Choice:
Whether we place a left or right paren at a certain decision point in our recursion.
Our Constraints:
We can't place a right paren unless we have left parens to match against.
Our Goal:
Place all k left and all k right parens.
The Key
At each point of constructing the string of length 2k we make a choice.
We can place a "(" and recurse or we can place a ")" and recurse.
But we can't just do that placement, we need 2 critical pieces of information.
The amount of left parens left to place.
The amount of right parens left to place.
We have 2 critical rules at each placement step.
We can place a left parentheses if we have more than 0 left to place.
We can only place a right parentheses if there are left parentheses that we can match against.
We know this is the case when we have less left parentheses to place than right parentheses to place.
Once we establish these constraints on our branching we know that when we have 0 of both parens to place that we are done, we have an answer in our base case.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 16.6 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
Видео Generate All Strings With n Matched Parentheses - Backtracking ("Generate Parentheses" on LeetCode) канала Back To Back SWE
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
Amazon System Design Interview: Design Parking GarageEp.1: Depth-First Search - LeetCode Problems That Got Me HiredAll Nodes Distance K In A Binary Tree - Performing Bidirectional Search On A Tree Using A HashtableGenerate Parentheses - Stack - Leetcode 22The Backtracking Blueprint: The Legendary 3 Keys To Backtracking AlgorithmsGenerate all Balanced ParenthesesTotal Ways To Decode A String - Recursive Dynamic Programming Approach ("Decode Ways" on LeetCode)Maximum Sum Rectangle In A 2D Matrix - Kadane's Algorithm Applications (Dynamic Programming)Count Total Unique Binary Search Trees - The nth Catalan Number (Dynamic Programming)How To Get A Job At Google | The Ultimate Guide To Algorithmic/Coding InterviewsThe Science of Six Degrees of SeparationImplement An LRU Cache - The LRU Cache Eviction Policy ("LRU Cache" on LeetCode)Max Contiguous Subarray Sum - Cubic Time To Kadane's Algorithm ("Maximum Subarray" on LeetCode)The Change Making Problem - Fewest Coins To Make Change Dynamic ProgrammingMerge K Sorted Arrays - Min Heap Algorithm ("Merge K Sorted Lists" on LeetCode)LeetCode 22. Generate ParenthesesDeeply Understanding Logarithms In Time Complexities & Their Role In Computer Science6 Introduction to Backtracking - Brute Force ApproachA slacker was 20 minutes late and received two math problems… His solutions shocked his professor.