Backtracking Algorithm Practice: Generating Valid Parentheses
Note
Now all the plugins has supported English. I'm still improving the website...
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 22. Generate Parentheses | 🟠 |
Prerequisite Knowledge
Before reading this article, you should first learn:
The parentheses problem can be broadly categorized into two types: one is determining the validity of parentheses, and the other is generating valid parentheses. To check the validity of parentheses, we primarily use the data structure known as a "stack." For generating parentheses, we generally use the backtracking algorithm to perform brute-force enumeration.
Now, let's focus on LeetCode Problem 22, "Generate Parentheses," with the following requirements:
22. Generate Parentheses | 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
The function signature is as follows:
List<String> generateParenthesis(int n);vector<string> generateParenthesis(int n);def generateParenthesis(n: int) -> List[str]:func generateParenthesis(n int) []stringvar generateParenthesis = function(n) {};Regarding the problem of parentheses, you just need to remember the following properties, and the solution will be easy to figure out: