Hello everyone, today I’m going to share with you the next LeetCode medium difficulty problem [22. Parenthesis generation]

The title

The number n represents the logarithm of parentheses generated. Design a function that generates all possible and valid parentheses combinations.

The combination of valid brackets must meet the following requirements: The left bracket must be closed in the correct sequence.

Example 1:

Input: n = 3 output: [” ((())) “, “() () ()”, “() () ()”, “() () ()”, “() () ()”] example 2:

Output: [“()”]

Analysis of the

1. Parentheses must match and have only parentheses

2. The left parenthesis can always be added but cannot be greater than or equal to n

3. The number of closing parentheses must be smaller than that of opening parentheses

4. Return an array of all parentheses

solution

1. The recursion

2. Violence

Solution a:recursive

1. If both left and right reach n, push the answer to 2 in res. 1. STR is null 2. Left has not reached n 2. Add close parenthesis 1. the last element of STR is (2. The number of close parentheses is less than the number of open parentheses 3. Return res */ var generateParenthesis = function (n) {const res = []; Function recursion(left, right, STR) {// Recursion (left, right, STR) { If (left === n && right === n) {res.push(STR); return; } // addParenthesis addParenthesis(left, right, n, STR); } function addParenthesis(left, right, n, str) { const strArr = str.split(""); const lastItem = strArr[strArr.length - 1]; 1. STR is null 2. Left has not reached n */ if (! strArr.length || left < n) { recursion(left + 1, right, n, str + "("); } / * 2. The add right parenthesis 1. STR is the last element (2) right number less than the left parenthesis * / brackets if (lastItem = = = "(" | | right (left) {recursion (left and right + 1, n, str + ")"); } } recursion(0, 0, n, ""); return res; }; /* Complexity time O(2^n) space O(n) */Copy the code

Method 2:violence

Generate all parenthesis combinations. Filter 3 by checking whether parentheses are valid. Return res */ var generateParenthesis = function (n) {const res = []; GenerateAll (n, ""); return res.filter((item) => { return valid(item); }); function generateAll(n, If (str.length === 2 * n) {res.push(STR); // If (str.length === 2 * n) {res.push(STR); return; } // generateAll(n, STR + "("); generateAll(n, str + ")"); Function valid(STR) {const stack = []; for (const s of str) { if (s === "(") { stack.push(s); } else { if (! stack.length || stack.pop() ! == "(") { return false; } } } return stack.length === 0; }}; /* Complexity time O(2^n) space O(n) */Copy the code

conclusion

Today’s problem is really just an exercise in understanding recursion. How do I recursively generate parentheses and filter qualified pairs of parentheses using conditions

You can have a look at a column I share (front-end algorithm) where there are more topics about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me to like, thank you very much

If you’re interested in “TS” check out my column (TypeScript common knowledge) and thank you for supporting it

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Some of the materials in this article are from the network. If there is infringement, please contact to delete, [email protected]

\