Shulou(Shulou.com)05/31 Report--

This article introduces the knowledge of "how to generate parentheses on C++". In the operation of actual cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Generate Parentheses generates parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[

"(())

"() ()

"() ()

"() ()"

()

]

Given a number n, let all the correct forms of n parentheses be generated. For this kind of problem listing all the results, we should first consider using recursive Recursion to solve the problem. Because the string has only two characters: left parenthesis and right parenthesis, and the final result must be 3 left parentheses and 3 right parentheses, two variables left and right are defined here to represent the number of left and right parentheses, respectively. The number of left parentheses is greater than the number of closing parentheses, indicating that the number of right parentheses in the generated string is greater than the number of left parentheses, that is, an illegal string such as ") (" will appear, so this case is returned directly without further processing. If both left and right are 0, the string generated at this time already has 3 left parentheses and 3 right parentheses, and the string is legal, it will be saved in the result and returned. If the above two situations are not satisfied, if the left is greater than 0, the recursive function is called. Pay attention to the update of the parameters. If the right is greater than 0, the recursive function is called, and the parameters are also updated. See the code as follows:

C++ solution one:

Class Solution {public: vector generateParenthesis (int n) {vector res; generateParenthesisDFS (n, n, ", res); return res;} void generateParenthesisDFS (int left, int right, string out, vector & res) {if (left > right) return; if (left = = 0 & & right = = 0) res.push_back (out) Else {if (left > 0) generateParenthesisDFS (left-1, right, out + "(", res); if (right > 0) generateParenthesisDFS (left, right-1, out + "), res);}

Java solution 1:

Public class Solution {public List generateParenthesis (int n) {List res = new ArrayList (); helper (n, n, "", res); return res;} void helper (int left, int right, String out, List res) {if (left)

Right) return; if (left = = 0 & & right = = 0) {res.add (out); return;} helper (left-1, right, out + "(", res); helper (left, right-1, out + "), res);}}

Let's take a look at that method. This method is a method given in CareerCup books, and it feels like an ingenious method. The idea of this method is to find the left parenthesis, every time you find a left parenthesis, add a complete parenthesis after it, and finally add a () at the beginning, which forms all the cases. It should be noted that sometimes there will be repetitions, so use set data structures. The advantage is that if duplicates are encountered, they will not be added to the result. Finally, we can change set to vector, as shown in the following code:

Numb1: ()

Numb2: (()) () ()

(()) ()

C++ solution 2:

Class Solution {public: vector generateParenthesis (int n) {unordered_set st; if (n = 0) st.insert (""); else {vector pre = generateParenthesis (n-1); for (auto a: pre) {for (int I = 0; I < a.size () + + I) {if (a [I] = = "(") {a.insert (a.begin () + I + 1, "("); a.insert (a.begin () + I + 2, ")); st.insert (a) A.erase (a.begin () + I + 1, a.begin () + I + 3);}} st.insert ("()" + a);}} return vector (st.begin (), st.end ());}}

Java solution II:

Public class Solution {public List generateParenthesis (int n) {Set res = new HashSet (); if (n = = 0) {res.add (");} else {List pre = generateParenthesis (n-1); for (String str: pre) {for (int I = 0; I < str.length ()) + + I) {if (str.charAt (I) = "(") {str = str.substring (0, I + 1) + "()" + str.substring (I + 1, str.length ()); res.add (str) Str = str.substring (0, I + 1) + str.substring (I + 3, str.length ());} res.add ("()" + str);}} return new ArrayList (res) This is the end of the introduction of "how C++ generates parentheses". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.