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 ->
- We are using isValid(parenthesis) ->bool which will tell us if the string formed during our process is valid or not.
- We are using generate recursive function to generate possible string parenthesis.
- 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.
