22. Generate Parentheses

MediumStringDynamic ProgrammingBacktracking

Problem Description

The problem requires us to generate all possible combinations of well-formed parentheses given n pairs. A well-formed combination of parentheses means that each opening bracket "(" has a corresponding closing bracket ")", and they are correctly nested. To better understand, for n=3, one such correct combination would be "((()))", whereas "(()" or "())(" would be incorrect formations.

Flowchart Walkthrough

Let's employ the algorithm flowchart to determine how to approach solving LeetCode Problem 22: Generate Parentheses. Here’s a step-by-step analysis:

Is it a graph?

No: The problem involves generating combinations of parentheses, which does not fit the typical graph scenario of nodes and edges.

Need to solve for kth smallest/largest?

No: This problem is about generating valid parentheses combinations, not about ordering or finding specific positions like smallest or largest values.

Involves Linked Lists?

No: The problem does not involve traversing or manipulating linked lists.

Does the problem have small constraints?

Yes: The problem is confined to generating combinations for a relatively small number of pairs of parentheses, making exhaustive exploration feasible.

Brute force / Backtracking?

Yes: The need to explore all valid combinations where the sequence of parentheses must be valid suggests using a backtracking approach. Backtracking helps in systematically building up solutions and abandoning invalid ones early.

Conclusion: According to the flowchart, using a backtracking pattern is appropriate for efficiently generating all valid combinations of parentheses, given the constraints and the structure of the problem.

Intuition

To arrive at the solution, we need to think about how we can ensure we create well-formed parentheses. For that, we use Depth First Search (DFS), which is a recursive method to explore all possible combinations of the parentheses.

We start with an empty string and at each level of the recursion we have two choices: add an opening parenthesis "(" or a closing parenthesis ")".
However, we have to maintain the correctness of the parentheses. This means we cannot add a closing parenthesis if there are not enough opening ones that need closing.
We keep track of the number of opening and closing parentheses used so far. We are allowed to add an opening parenthesis if we have not used all n available opening parentheses.
We can add a closing parenthesis if the number of closing parentheses is less than the number of opening parentheses used. This ensures we never have an unmatched closing parenthesis.
We continue this process until we have used all n pairs of parentheses.
When both the opening and closing parentheses counts equal n, it means we have a valid combination, so we add it to our list of answers.

The code uses a helper function dfs which takes 3 parameters: the number of opening and closing parentheses used so far (l and r), and the current combination of parentheses (t).

By calling this function and starting our recursion with 0 used opening and closing parenthesis and an empty string, we will explore all valid combinations and store them in the list ans.

Learn more about Dynamic Programming and Backtracking patterns.

Solution Approach

The solution uses the DFS (Depth First Search) algorithm to generate the combinations. It employs recursion as a mechanism to explore all possible combinations and backtracks when it hits a dead end (an invalid combination).

Here's a step-by-step breakdown of the DFS algorithm as implemented in the provided solution:

Initial Call: The generateParenthesis function initiates the process by calling the nested dfs (Depth First Search) function with initial values of zero used opening parentheses (l), zero used closing parentheses (r), and an empty string for the current combination (t).
DFS Function: This is the recursive function that contains the logic for the depth-first search. It takes three parameters:
- l: The number of opening parentheses used so far.
- r: The number of closing parentheses used so far.
- t: The current combination string formed by adding parentheses.
Base Case: The recursion has two base cases within the DFS function: a. Invalid Condition: When the number of used opening parentheses l is more than n, or the closing parentheses r is more than n or more than l, it indicates an incorrect combination. The function returns without doing anything. b. Valid Combination: When both l and r equal n, it indicates that a valid combination of parentheses has been found. The current combination string t is added to the solution set ans.
Recursive Exploration: If neither base case is met, the function continues to explore:
- Adding an opening parenthesis: If not all n opening parentheses have been used (l < n), the dfs function calls itself with l + 1, r, and appends "(" to the current string t.
- Adding a closing parenthesis: If the number of closing parentheses used is less than the number of opening parentheses (r < l), it implies that there are some unmatched opening parentheses. Thus, the dfs function calls itself with l, r + 1, and appends ")" to t.

By calling these two lines of code, we ensure that we explore the decisions to either add an opening parenthesis or a closing one, thus generating all valid paths.

Storage of Valid Combinations: The ans list is the container that holds all valid combinations. Each time a complete valid combination is generated, it's added to this list. After all recursive calls are completed, ans will contain all the possible well-formed parentheses combinations.
Return Result: Finally, once all possible combinations have been explored, the ans list is returned as the result of the generateParenthesis function.

This implementation provides a sleek and efficient way to solve the problem of generating all combinations of well-formed parentheses, relying solely on the DFS strategy without needing any additional complex data structures.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example where n = 2, meaning we want to generate all combinations of well-formed parentheses for 2 pairs.

Step 1: Initial Call
The generateParenthesis function begins by making an initial call to dfs with l = 0, r = 0, and t = "" (an empty string).

Step 2: First Level Recursive Calls
At this stage, we have two choices: add an opening parenthesis or add a closing parenthesis. Since l < n, we can add an opening parenthesis. We cannot add a closing parenthesis yet because r < l is not satisfied (both l and r are 0). So, our recursive calls are:

dfs(1, 0, "(")

Step 3: Second Level Recursive Calls
After the first opening parenthesis is added, we are again at a stage where we can choose to add an opening or closing parenthesis. The string is now "(".

For l < n, which is true (1 < 2), we add another opening parenthesis: dfs(2, 0, "((").
We still cannot add a closing parenthesis yet as r is not less than l (r < l is not true).

Step 4: Third Level Recursive Calls
We now have the string "((" and l = 2, r = 0. We cannot add any more opening parentheses because l is not less than n anymore (2 is not less than 2). We must add a closing parenthesis now since r < l is satisfied. We get:

dfs(2, 1, "(()")

Step 5: Fourth Level Recursive Calls
Our current string is "(()" and l = 2, r = 1. We still satisfy the condition r < l, so we can add another closing parenthesis:

dfs(2, 2, "(())")

Step 6: Base Case Reached
Now l = 2 and r = 2, which equals n. We have reached a base case where we have a well-formed combination. This combination "(())" is added to our answer set ans.

Backtracking
The algorithm will backtrack now and explore other paths, but since n = 2 and we have used all our opening parentheses, there are no more paths to discover.

Step 7: Return Result
The completed list ans, now containing "(())", is returned.

Considering another branch of this example, if we go back to the second level again and instead of adding another opening parenthesis, we decide to add a closing parenthesis:

After the first level, we have "(".
Add a closing parenthesis: dfs(1, 1, "()"), because we can add a closing parenthesis as r < l.
Now, we have l = 1 and r = 1, we can add an opening parenthesis: dfs(2, 1, "()(").
We can only add a closing parenthesis now: dfs(2, 2, "()()").

So the complete set of combinations for n = 2 is "(())" and "()()".

Solution Implementation

1class Solution:
2    def generateParenthesis(self, n: int) -> List[str]:
3        # Helper function for depth-first search
4        def backtrack(open_count, close_count, path):
5            # If there are more open or more close parens than 'n', or more close parens than open, it's invalid
6            if open_count > n or close_count > n or open_count < close_count:
7                return
8            # When the current path uses all parens correctly, add the combination to the results
9            if open_count == n and close_count == n:
10                combinations.append(path)
11                return
12            # Continue the search by adding an open paren if possible
13            backtrack(open_count + 1, close_count, path + '(')
14            # Continue the search by adding a close paren if possible
15            backtrack(open_count, close_count + 1, path + ')')
16
17        # This list will hold all the valid combinations
18        combinations = []
19        # Start the recursive search with initial counts of open and close parentheses
20        backtrack(0, 0, '')
21        # Return all the valid combinations found
22        return combinations
23

1class Solution {
2    // List to hold all the valid parentheses combinations
3    private List<String> answers = new ArrayList<>();
4    // The number of pairs of parentheses
5    private int maxPairs;
6
7    /**
8     * Generates all combinations of n pairs of well-formed parentheses.
9     *
10     * @param n the number of pairs of parentheses
11     * @return a list of all possible combinations of n pairs of well-formed parentheses
12     */
13    public List<String> generateParenthesis(int n) {
14        this.maxPairs = n;
15        // Start the depth-first search with initial values for open and close parentheses count
16        generate(0, 0, "");
17        return answers;
18    }
19
20    /**
21     * Helper method to generate the parentheses using depth-first search.
22     *
23     * @param openCount  the current number of open parentheses
24     * @param closeCount the current number of close parentheses
25     * @param currentString the current combination of parentheses being built
26     */
27    private void generate(int openCount, int closeCount, String currentString) {
28        // Check if the current counts of open or close parentheses exceed maxPairs or if closeCount exceeds openCount
29        if (openCount > maxPairs || closeCount > maxPairs || openCount < closeCount) {
30            // The current combination is invalid, backtrack from this path
31            return;
32        }
33        // Check if the current combination is a valid complete set of parentheses
34        if (openCount == maxPairs && closeCount == maxPairs) {
35            // Add the valid combination to the list of answers
36            answers.add(currentString);
37            return;
38        }
39        // Explore the possibility of adding an open parenthesis
40        generate(openCount + 1, closeCount, currentString + "(");
41        // Explore the possibility of adding a close parenthesis
42        generate(openCount, closeCount + 1, currentString + ")");
43    }
44}
45

1class Solution {
2public:
3    // Function to generate all combinations of well-formed parentheses.
4    vector<string> generateParenthesis(int n) {
5        vector<string> result; // This will store the valid combinations.
6
7        // Use a lambda function to perform depth-first search.
8        // 'leftCount' and 'rightCount' track the count of '(' and ')' used respectively.
9        // 'current' is the current combination of parentheses.
10        function<void(int, int, string)> depthFirstSearch = [&](int leftCount, int rightCount, string current) {
11            // If the current combination is invalid (more ')' than '(' or counts exceed 'n'), stop exploration.
12            if (leftCount > n || rightCount > n || leftCount < rightCount) return;
13
14            // If the combination is valid and complete, add it to the result list.
15            if (leftCount == n && rightCount == n) {
16                result.push_back(current);
17                return;
18            }
19
20            // If we can add a '(', do so and continue the search.
21            depthFirstSearch(leftCount + 1, rightCount, current + "(");
22
23            // If we can add a ')', do so and continue the search.
24            depthFirstSearch(leftCount, rightCount + 1, current + ")");
25        };
26
27        // Start the search with zero counts and an empty combination.
28        depthFirstSearch(0, 0, "");
29      
30        // Return all the valid combinations found.
31        return result;
32    }
33};
34

1function generateParenthesis(n: number): string[] {
2    // Define the result array to store valid combinations of parentheses.
3    let result: string[] = [];
4
5    // Define a depth-first search function to explore all possible combinations of parentheses.
6    // l: count of left parentheses used, r: count of right parentheses used, currentString: current combination of parentheses
7    function depthFirstSearch(leftCount: number, rightCount: number, currentString: string): void {
8        // If the number of left or right parentheses exceeds n, or if the number of right parentheses
9        // is greater than the left at any point, the current string is invalid.
10        if (leftCount > n || rightCount > n || leftCount < rightCount) {
11            return;
12        }
13
14        // If the current string uses all left and right parentheses correctly, add it to the result.
15        if (leftCount === n && rightCount === n) {
16            result.push(currentString);
17            return;
18        }
19
20        // Explore further by adding a left parenthesis if it does not exceed the limit.
21        depthFirstSearch(leftCount + 1, rightCount, currentString + '(');
22      
23        // Explore further by adding a right parenthesis if it does not exceed the limit.
24        depthFirstSearch(leftCount, rightCount + 1, currentString + ')');
25    }
26
27    // Start the depth-first search with a count of 0 for both left and right parentheses and an empty string.
28    depthFirstSearch(0, 0, '');
29
30    // Return the array of valid combinations.
31    return result;
32}
33

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(4^n / sqrt(n)). This complexity arises because each valid combination can be represented by a path in a decision tree, which has 2n levels (since we make a decision at each level to add either a left or a right parenthesis, and we do this n times for each parenthesis type). However, not all paths in the tree are valid; the number of valid paths follows the nth Catalan number, which is proportional to 4^n / (n * sqrt(n)), and n is a factor that represents the polynomial part that gets smaller as n gets larger. Since we're looking at big-O notation, we simplify this to 4^n / sqrt(n) for large n.

Space Complexity

The space complexity is O(n) because the depth of the recursive call stack is proportional to the number of parentheses to generate, which is 2n, and the space required to store a single generated set of parentheses is also linear to n. Hence, the complexity due to the call stack is O(n). The space used to store the answers is separate and does not affect the complexity from a big-O perspective. Keep in mind that the returned list itself will contain O(4^n / sqrt(n)) elements, and if you consider the space for the output list, the overall space complexity would be O(n * 4^n / sqrt(n)), which includes the length of each string times the number of valid strings. Typically, the space complexity considers only the additional space required, not the space for the output. Therefore, we only consider the O(n) space used by the call stack for our space complexity analysis.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know