Skip to Content

Generate valid parentheses

Home | Coding Interviews | Stacks and Queues | Generate valid parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

 public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<String>();
        backtrack(list, "", 0, 0, n);
        return list;
    }
    
    public void backtrack(List<String> list, String str, int open, int close, int max){
        
        if(str.length() == max*2){
            list.add(str);
            return;
        }
        
        if(open < max)
            backtrack(list, str+"(", open+1, close, max);
        if(close < open)
            backtrack(list, str+")", open, close+1, max);
    }

Posted by Jamie Meyer 3 months ago

Related Problems

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.

void push(int val) pushes the element val onto the stack.

void pop() removes the element on the top of the stack.

int top() gets the top element of the stack.

int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.