Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Balanced Parentheses

Problem Statement

For a given number ‘N’, write a function to generate all combination of ‘N’ pairs of balanced parentheses.

Example 1:

Input: N=2
Output: (()), ()()

Example 2:

Input: N=3
Output: ((())), (()()), (())(), ()(()), ()()()

Constraints:

  • 1 <= n <= 8

Solution

This problem follows the Subsets pattern and can be mapped to Permutations. We can follow a similar BFS approach.

Let’s take Example-2 mentioned above to generate all the combinations of balanced parentheses. Following a BFS approach, we will keep adding open parentheses `(

.....

.....

.....

Like the course? Get enrolled and start learning!
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def generateValidParentheses(self, num):
   
    def backtrack(result, combo, left_count, right_count):
      
      if len(combo) == 2 * num:
        result.append(combo)
        return
      
      if left_count < num:
        backtrack(result, combo + '(', left_count + 1, right_count)
      
      if right_count < left_count:
        backtrack(result, combo + ')', left_count, right_count + 1)
    
    result = []
    backtrack(result, '', 0, 0)
    return result
L

lejafilip

· 2 years ago

It is most common way to solve this problem.

I

Ivy

· 4 years ago

At each step, isn't it simpler to just add the pair of parentheses by either enclosing or appending to the previous combinations? e.g. Step 1: () Step 2: ()() (()) Step 3: ()()(), (()()) (())(), ((())) I believe the string operations would cost the same amount of time as well, so I don't think this solution compromises on any space-time efficiency.

Show 1 reply
Ben

Ben

· 2 years ago

Hey,

the constraints for this are: 1 <= n <= 8

Yet, one of the test cases is n = 0 :)

Debasis B

Debasis B

· a year ago

    List<string> result = new List<string>();
    
    public List<string> generateValidParentheses(int num)
    {
        generate(new List<string>(), numOpen: 0, numClose: 0, num);
        return result;
    }

    private void generate(List<string> list, int numOpen, int numClose, int num)
    {
        // Base case: count of open and close equals num
        if (numOpen == num && numClose == num)
        {
            result.Add(string.Concat(list));
            return;
        }
        // Deadend: num of open less than num of close
        if (numOpen < numClose) return;
        // Recursively generate with open paren if open paren can be added
        if (numOpen < num)
        {
            list.Add("(");
            generate(list, numOpen + 1, numClose, num);
Vishwajeet Thoke

Vishwajeet Thoke

· 2 months ago

using namespace std;

#include <iostream>
#include <queue>
#include <string>
#include <vector>

class Solution {
   public:
    vector<string> generateValidParentheses(int num) {
        vector<string> result;
        if (num == 0)
            return vector<string>{""};
        queue<string> q;
        q.push("");
        while (!q.empty()) {
            string previousStr = q.front();
            q.pop();
            int k = 0;
            while (k <= previousStr.length() / 2) {
                string newStr = previousStr;
                newStr.insert(k, "()");
                if (newStr.length() == num * 2) {
                    result.push_back(newStr);
                } else {
                    q.push(newStr);
                }
                if (previousStr[k] == ')')