Title link: 22. Parenthesis generation

Title description:

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

Example 1:
Input: n = 3 output: [" ((())) ", "() () ()", "() () ()", "() () ()", "() () ()"]Copy the code
Example 2:
Output: ["()"]Copy the code
Tip:
1 <= n <= 8
Copy the code

Directions: For this part,

This is a classic backtracking problem, and we all know that to solve a backtracking problem, we need to implement a traversal decision.

Back to the question, first of all, we know that parentheses exist in pairs, and there are open parentheses before close parentheses, so we only add close parentheses if the number of close parentheses is less than the number of open parentheses. In other words, the backtracking condition for this problem is that the left and right parentheses are all lined up.

And then finally, if the number of close parentheses is equal to 0, that means that the close parentheses are exhausted, and that means that the open parentheses are exhausted.

Let’s look at the implementation of this solution:

Code implementation:

Func generateParenthesis(n int) []string {// Use new method to create memory return memory address res := new([]string) backtracking(n, n, "", Res) return *res} func backtracking(left, right int, TMP string, res *[]string) { Because the condition right > left generated by the close bracket, */ if right == 0 {*res = append(*res, If left > 0 {backtracking(left-1, right, TMP + "(", res)}} Backtracking (left, right-1, TMP + ")", res)}}Copy the code

Conclusion:

This problem with violence solution, breadth first algorithm, dynamic programming should be able to do, interested partners can try to achieve, and then compare the difference in execution efficiency, pay attention to empty processing.