This is the 9th day of my participation in Gwen Challenge

Title: Parenthesis generation

Address: leetcode-cn.com/problems/ge…

Title description:

The word n stands for the logarithm of generated parentheses. Design a function that generates all possible and valid combinations of parentheses.

Example 1:

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

Output: [“()”]

Tip:

1 <= n <= 8

Problem solving:

This question is somewhat similar to the alphabetic combination of telephone numbers that we have scanned for question 17. Think of it as a tree. Each time there are two choices.

When n=2, which is the case above, 2 pairs have 4 characters, all of which are possible as above 2^4 = 16, but the following conditions must be met for the parentheses to occur in pairs

1. The number of open parentheses cannot exceed n
2. The total number of closing parentheses at a time cannot be greater than the number of opening parentheses, which is less than or equal to

Backtracking code:

As you can see from the image above, the entire code works by backtracking (referring to the direction of the red line), iterating through to the last step, relying on the previous selection, and then returning to the previous step to make other choices when the last step is complete.

public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0.0, n);
        return ans;
    }

    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        if (open < max) {// The left parenthesis can still appear
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {// Append the close parenthesis
            cur.append(') ');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1); }}Copy the code

Question:

With these two brushes we found that backtracking is very similar to subsequent traversal of binary trees and depth-first search of graphs. At the same time, the running logic of this topic and dynamic programming also have some ideas. Now, if we can do the same thing with this problem, if we keep all the possibilities for each loop, the boundary condition is that we end up with more open parentheses than n and more close parentheses than open parentheses. But how do we choose the corresponding approach?