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!

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);