Generate Parentheses

title: Generate Parentheses tags: combination backtracking

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

Thinking Process

Classify the Problem Type

Look for clues in the problem space.

Generate all combinations - Exhaustive Enumeration

Define the Interface

Input: n (integer) Output: Array of strings

Define the Term

Well Formed

You cannot begin with closed parenthesis
You cannot end with open parenthesis

Cases

n = 1, ‘()’ The size of the well formed parenthesis is n * 2 n = 2 ) - Not possible ( - Possible Two possible second choices, either closed or open
() (( () ()( ()() - One possible answer
(( (()). - Second possible answer

n = 3

The first choice we can make is only ( The second choice can either be another ( or ) The third choice will be ( (

            (                    )
        
    (              )            (     -
    
-     )       (         )     (     )
     
   -    )   -    )    (    -  -  )  ( -
   
     -     )   -   ) -  )         ) - )

Possible Parentheses Variations

((())) (()()) (())() ()(()) ()()()

What are the options? Open and Close.
What are the choices we have to make at every level? Well formed parenthesis means you cannot have a closing parenthesis without a open parenthesis. Unless you have more than 0 open parenthesis, you cannot choose a close parenthesis. At every level, you must maintain the invariant (Well formed parenthesis).
We will start with an empty string and construct a well formed parenthesis, when we reach the leaf node we will get one of the possible combinations.
What is the base case?
- When should we stop the recursion?
- When the length of the string is equal to 2 * n
- Pruning the tree. We will choose closed parenthesis unless we have at least one open parenthesis
How do we keep track of how many open / close parenthesis are present in the partial? We can have the open and close as counters, pass it in as parameters to the recursive call.
Unit of work
- What is the smallest unit of work that each recursive call must make?
- Check if the current string is valid.
- Picking either open or close parenthesis. UoW is done before the recursive call.
How many subproblems do we have? Resembles the include-exclude. Two recursive calls

Time and Space Complexity

Time: O( ) Space: O( )

Key Takeaways

Choices - Pick from the given options
Invariant - We cannot violate the invariant during any of the recursive calls
Cloning of the combination is not required (not like an array)
If we pass the combination by concatenating, we can eliminate the backtrack step (removing the parenthesis we picked)
If we don’t concatenate, then we need to have the backtrack step to unchoose the parenthesis that was chosen before.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def backtrack(n, open, close, combination, output)
  if combination.size == n * 2
    output << combination
		
    return
  end
  
  # Unit of Work
  if open < n
    backtrack(n, open+1, close, combination + '(', output)
  end
    
  if open - close > 0
    backtrack(n, open, close+1, combination + ')', output)
  end
end

# @param {Integer} n
# @return {String[]}
def generate_parenthesis(n)
  output = []
  combination = ''

  backtrack(n, 0, 0, combination, output)
  output
end

To generate all combinations of well-formed parentheses, we can use a recursive approach. The basic idea is to keep track of the number of open and close parentheses that are still available to be added to the current combination.

Here’s a step-by-step approach:

Create a recursive function that takes the current combination, the number of open parentheses available, and the number of close parentheses available.
If there are no more open or close parentheses available, add the current combination to the result list.
If there are open parentheses available, add an open parenthesis to the current combination, and call the recursive function with one fewer open parenthesis available.
If there are more close parentheses available than open parentheses, add a close parenthesis to the current combination, and call the recursive function with one fewer close parenthesis available.
Continue this process until all combinations are explored.

Here’s the code implementing this approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate_combinations(current, open_count, close_count, result):
            # If there are no more parentheses available, add the combination to the result
            if open_count == 0 and close_count == 0:
                result.append(current)
                return

            # If there are open parentheses available, add one and recurse
            if open_count > 0:
                generate_combinations(current + "(", open_count - 1, close_count, result)

            # If there are more close parentheses available than open, add one and recurse
            if close_count > open_count:
                generate_combinations(current + ")", open_count, close_count - 1, result)

        result = []
        generate_combinations("", n, n, result)
        return result

The time complexity of this solution is (O(\frac{4^n}{\sqrt{n}})), and the space complexity is (O(\frac{4^n}{\sqrt{n}})) as well, as there are a total of (C_{2n}^n) valid combinations, where (C) denotes the binomial coefficient.

Identifying Problem Isomorphism

“Generate Parentheses” involves generating all combinations of well-formed parentheses for a given number ’n’.

A simpler problem that involves combinatorial generation, but without the constraint of well-formedness is “Subsets”. Here, you are given a distinct set of integers and you need to generate all possible subsets.

An approximate isomorphic problem is “Letter Case Permutation”, where you are given a string and need to generate all possible strings with case changes. The concept of generating all possible permutations mirrors the combinatorial aspect of the “Generate Parentheses” problem.

A more complex problem is “N-Queens”. In this problem, you have to place N queens on an N×N chessboard so that no two queens threaten each other. This involves the generation of valid combinations similar to “Generate Parentheses”, but with a higher degree of complexity due to the spatial nature of the problem.

So, from simplest to more complex:

“Subsets” - Generate all possible subsets of a set.
“Generate Parentheses” - Generate all combinations of well-formed parentheses for a given number ’n'.
“Letter Case Permutation” - Given a string, generate all possible strings with case changes.
“N-Queens” - Place N queens on an N×N chessboard so that no two queens threaten each other. Generate all valid combinations.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def generateParenthesis(self, n: int) -> List[str]:
	def dfs(left, right, s):
		if len(s) == n * 2:
			res.append(s)
			return 

		if left < n:
			dfs(left + 1, right, s + '(')

		if right < left:
			dfs(left, right + 1, s + ')')

	res = []
	dfs(0, 0, '')
	return res

Problem Classification

Language Agnostic Coding Drills

Understanding function definition: Understand how to define functions with or without arguments and how to call them.
Understand basic data types: Understand how to work with basic data types like integers and strings.
Understanding lists: Understand how to declare and manipulate lists.
Understanding recursion: Understand the concept of recursion, where a function calls itself.
Conditional statements: Understand how to write if conditions to control the flow of the program.
Manipulating strings: Understand how to concatenate strings.
Understanding the principle of depth-first-search: This is a more advanced topic where the function dfs is a depth-first search function which recursively explores all possibilities.
Understanding the problem domain: The problem is about generating valid parentheses, which means understanding the conditions under which parentheses are valid.

Here is the list arranged in increasing level of difficulty:

Understanding function definition
Understand basic data types
Understanding lists
Conditional statements
Manipulating strings
Understanding recursion
Understanding the problem domain
Understanding the principle of depth-first-search

Each of the concepts can be practiced separately and then gradually combined to understand and implement the full solution.

Targeted Drills in Python

Understanding function definition:

1
2
3
4
# Drill: Define a function that takes two numbers as input and returns their sum.
def add(a, b):
    return a + b
print(add(3, 2))  # Expected output: 5

Understand basic data types:

1
2
3
4
5
# Drill: Create two variables, one with an integer value and one with a string, and print their types.
a = 5
b = "Hello"
print(type(a))  # Expected output: <class 'int'>
print(type(b))  # Expected output: <class 'str'>

Understanding lists:

1
2
3
4
# Drill: Create a list of numbers and print the list and its length.
numbers = [1, 2, 3, 4, 5]
print(numbers)  # Expected output: [1, 2, 3, 4, 5]
print(len(numbers))  # Expected output: 5

Conditional statements:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
# Drill: Write a conditional statement that prints whether a number is positive, negative, or zero.
def check_number(n):
    if n > 0:
        print("Positive")
    elif n < 0:
        print("Negative")
    else:
        print("Zero")

check_number(5)  # Expected output: Positive
check_number(-3)  # Expected output: Negative
check_number(0)  # Expected output: Zero

Manipulating strings:

1
2
3
4
5
# Drill: Concatenate and print two strings.
greeting = "Hello, "
name = "World"
message = greeting + name
print(message)  # Expected output: Hello, World

Understanding recursion:

1
2
3
4
5
6
7
# Drill: Write a recursive function to calculate the factorial of a number.
def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n-1)
print(factorial(5))  # Expected output: 120

Understanding the problem domain:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# Drill: Write a function to check if a string of parentheses is valid.
def is_valid_parentheses(s):
    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:
                return False
            stack.pop()
    return not stack  # If the stack is empty, the parentheses are valid

print(is_valid_parentheses('()()'))  # Expected output: True
print(is_valid_parentheses('(()('))  # Expected output: False

Understanding the principle of depth-first-search:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# Drill: Write a function to implement depth-first search on a tree.
class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children if children is not None else []

def dfs(node):
    print(node.value)
    for child in node.children:
        dfs(child)

# Test the function with a tree.
tree = Node(1, [Node(2), Node(3, [Node(4), Node(5)])])
dfs(tree)  # Expected output: 1 2 3 4 5