Generate-Parentheses Brute Force to Optimal Leetcode

We use backtracking in brute force approach
1) We make a choice and hope it’s a valid one, if it happens to be valid we proceed forward
2) If the option we chose earlier happens to be wrong we go back one step to pick alternate choice, If we run out of the alternatives, we go back another step, we continue our search in this way.

Like most recursions this is Depth First Search if you visualize the recursion tree.

The code should be self explanatory ->

  1. We are using isValid(parenthesis) ->bool which will tell us if the string formed during our process is valid or not.
  2. We are using generate recursive function to generate possible string parenthesis.
  3. At every point we have two options — either we can pick ‘(‘ or ‘)’ and we append it to our track string and continue forward until the length hits the input, then we run “isValid(track) and decide on how to proceed further.

Below is the CPP Implementation for the same.

Optimal Solution

This solution is based on GFG solution, again the code should be self explanatory, else GFG have a great explanation here

https://www.geeksforgeeks.org/print-all-combinations-of-balanced-parentheses/

Clap if this helped you.

Thanks for your time.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store