LeetCode Medium: Generate Parentheses

Dear followers,

Tonight, I came across a nice problem for post-dinner exercise, about generating all possible valid parentheses sequences given the number of brackets to use in total.

PROBLEM LINK: https://leetcode.com/problems/generate-parentheses/

PROBLEM SOLVING APPROACH: Recursion (using Choice Diagram and Decision tree)

TIME-COMPLEXITY: O(2^n) in the worst case but the input n is given to be max 8, so very much doable :)

Here's a sample Java solution for your reference:

class Solution {
    public List<String> generateParenthesis(int n) {
        ArrayList<String> generatedParentheses = new ArrayList<>();
        genParenthesesRecur(n, n, "", generatedParentheses);
        return generatedParentheses;
    }
    
    private void genParenthesesRecur (int remOpenBrackets, int remClosingBrackets, String outputFromCaller, List<String> generatedParentheses) {
        // Base Cases
        if (remOpenBrackets < 0 || remClosingBrackets < 0)
            return;
        
        if (remClosingBrackets < remOpenBrackets) {
            return;
        }
        
        if (remOpenBrackets == 0 && remClosingBrackets == 0) {
           generatedParentheses.add(outputFromCaller);
        }
        
        // Recursive Case
        String opUsingAnOpeningBracket = outputFromCaller + "(";
        genParenthesesRecur(remOpenBrackets-1, remClosingBrackets, opUsingAnOpeningBracket, generatedParentheses);
        if (remClosingBrackets > remOpenBrackets) {
            String opUsingAClosingBracket = outputFromCaller + ")";
            genParenthesesRecur(remOpenBrackets, remClosingBrackets-1, opUsingAClosingBracket, generatedParentheses);
        }
    }
}

Thanks for Reading!

Happy Programming!!

Love! ❤️ 
#Lets #Code

Follow us on :

https://twitter.com/ThinkAlgorithms

https://www.facebook.com/theAlgorithmicCoder