Generate Parentheses (#22 LeetCode)

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

 

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

 

Constraints:

• 1 <= n <= 8

There are various ways to solve this parentheses problem: 

1. Backtraking 

2. Dynamic Programming 

3. Stack 

Let's discuss this slightly more abstract way. There are 4 conditions I could figure it out if n is 3. 

1. n should be 3 

2. open & close parenthesis should be 3

3. Ordering of parenthesis matters

4. Number of close parentheses should be less than open while adding close parenthesis. 

The Whiteboard link is here.

1. Backtracking

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time (by time, here, is referred to the time elapsed till reaching any level of the search tree)

It does various permutations and combinations of the given number/input. 

It is 2^n problem or it is a kind of Bruteforce approach. 

It is an intuitive idea.

1. Usually backtracking involve list.

return-type someFunction(int n)
{
   list btList;
   btList.assign(n, 0); //Creates n nodes with value as 0
   backtrack(btList);
   return btList;  
}

void backtrack(list bt, string s) 
{
   if () { //Some Base Case
       bt.insert(it, s);
       return;
   }
}

2. It also involves decisions. These decisions can be achieved by recursive calls. 

class Solution {

public:
    vector<string> generateParenthesis(int n) {
        vector<string> result; 
        backtrack(result, "", 0, 0, n);
        return result;
    }
    
    void backtrack(vector<string> &result, string comb,
                  int openPrth, int closePrth, int max) {
        if (comb.length() == max * 2) {
            result.push_back(comb);
            return;
        }
        
        if (openPrth < max) {
            backtrack(result, comb + "(", openPrth + 1, closePrth, max);
        }
        if (closePrth < openPrth) {
            backtrack(result, comb + ")", openPrth, closePrth + 1, max);
        }
        
        return;
    }
};

3. Stack

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        stack<helper> s;
        s.push({"", n, 0});
        while (!s.empty()) {
            helper h = s.top();
            s.pop();
            if(h.leftpairs == 0 && h.remaining == 0) {
                result.push_back(h.s);
                continue;
            }
            
            if (h.leftpairs > 0) {
                s.push({h.s + "(", h.leftpairs-1, h.remaining+1});
                
            } 
            if (h.remaining > 0) {
                s.push({h.s + ")", h.leftpairs, h.remaining-1});
            }
            
            
        }
        return result;
    }
    
private:
    struct helper {
        string s;
        int leftpairs;
        int remaining;
    };
};

It is one of the top 100 Fortune Company of 2022's question, so don't miss it.

References :

Stack - https://www.youtube.com/watch?v=s9fokUqJ76A

Backtracking - https://www.youtube.com/watch?v=qBbZ3tS0McI

Solutions are taken from the Leetcode.