Backtracking Algorithm Practice: Generating Valid Parentheses
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 22. Generate Parentheses | 🟠 |
Prerequisite Knowledge
Before reading this article, you should first learn:
Bracket problems can be simply divided into two categories: one is the Bracket Validity Check, previously discussed, and the other is the generation of valid brackets. For checking bracket validity, the main tool is the "stack" data structure, while generating brackets typically requires using the Backtracking Algorithm for brute-force enumeration.
Back to the main topic, let's look at LeetCode Problem 22: Generate Parentheses, which is described as follows:
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: