Generate Parentheses Leetcode Solution

Problem Statement

The Generate Parentheses LeetCode Solution – “Generate Parentheses” states that given the value of n. We need to generate all combinations of n pairs of parentheses.

Return the answer in the form of a vector of strings of well-formed parentheses.

Example:

Input:  n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

Explanation:

• All well-formed parentheses are:- [“((()))”,”(()())”,”(())()”,”()(())”,”()()()”].

Input:  n = 1

Output: ["()"]

Explanation:

• All well-formed parentheses are:- [“()”].

Approach

Idea:

1. The main idea to solve this problem is to use Recursion.
2. The Brute force approach is to consider every type of parentheses at each index and go to the next step of recursion, and check whether this lead to valid well-formed parentheses? If Yes, store the string as our answer, otherwise backtrack.
3. For an efficient solution, Start with an empty string and n number of open and close brackets (since we need to form n pairs).
4. At each step of recursion, the following cases hold:
   1. Base Case: When a number of open and close brackets are both equal to n, store the current string as our answer.
   2. When the number of opening brackets is strictly less than n, we can place the open bracket now.
   3. When the number of closing brackets is strictly less than the number of closing brackets, we need to place the closing bracket now.
5. Whenever we’ll reach the base case, we will store the string formed into our answer which is the well-formed parentheses.
6. Return all the well-formed parentheses as our answer, in the form of a vector of strings.

Code

Generate Parentheses Leetcode C++ Solution:

class Solution {
public:
    vector<string> ans;
    void recurse(string s,int open,int close,int n){
        if(open==n and close==n){
            ans.push_back(s);
            return;
        }
        if(open<n)
            recurse(s+"(",open+1,close,n);
        if(close<open)
            recurse(s+")",open,close+1,n);
    }
    vector<string> generateParenthesis(int n) {
        recurse("",0,0,n);
        return ans;
    }
};

Generate Parentheses Leetcode Java Solution:

class Solution {
    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);
        }
    }
}

Complexity Analysis for Generate Parentheses Leetcode Solution

Time Complexity

The time complexity of the above code is O(2^(2N)) since in the worst case we need to consider every possibility of opening and closing brackets where N = the number of pairs we need to form.

Space Complexity

The space complexity of the above code is O(N).