Leetcode:Question22--Generate Parentheses

题描述

这里写图片描述

解解思维

  1. Get this question, the first thing to think about is the case where the brackets match will be wrong. The title only lists the correct bracket matching, so you need to observe the mismatch yourself.
  2. The first thing you can notice is that the left parenthesis always appears as the beginning, and the right parenthesis always appears as the last. Except for the two ends, the occurrence of the closing parenthesis must require that the left parenthesis be preceded. So the idea at the beginning is to build a stack to store the left parenthesis. When writing a left parenthesis to the string, push a left parenthesis to the stack. When the parentheses in the stack pop out, write a right to the string. brackets. Therefore, it can be guaranteed that the right parenthesis and the left parenthesis match.
  3. is another question of how to traverse all situations. Except for the head and tail, if the number of the left parenthesis does not reach the upper bound, then either the left parenthesis or the right parenthesis can be added. If the number of left parentheses is full, then only the right parenthesis can be added. Since each case is based on the previous situation, it is more appropriate to use recursion
  4. . Finally, a value is set to store all the strings, so a private object is declared.
  5. I found it here, in fact, the role of the stack is only used to record the number of left and right brackets, so you can set a variable to record without maintaining a stack. Therefore, when adding the left and right parentheses, only the following two situations are required:
    • The number of left parentheses is greater than the number of right parentheses
    • The number of left parentheses is less than the required number
    • begins with the left parenthesis and ends with the right parenthesis

码分析

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        string s = "";
        addBracket(0, 0, n, s);
        return result;
    }

    void addBracket(int left, int right, int max, string s) {
        if (s.size() == max * 2)
        {
            result.push_back(s);
            return;
        }
        else {
            if (left < max) {
                addBracket(left + 1, right, max, s + '(');   
            }
            if (right < left) {
                addBracket(left, right + 1, max, s + ')');
            }
        }

    }
private:
    vector<string> result;
};

This question is in C++ and is done using recursion. There was a bit of error in the code writing of the recursive process. At the beginning, I wrote an error with

    /-----/
        else {
            if (left < max) {
                addBracket(++left, right, max, s + '(');   
            }
            if (right < left) {
                addBracket(left, ++right, max, s + ')');
            }
        }

    /----/

. Debug found that when recursively to the string "(()", the number of left parentheses is displayed as 3, visible, in the previous step "((()))"), the recursion process returns to this step, the number of left parentheses is first An increment.

Next I tried again to put the auto-increment on the right (obviously already known to be wrong) and found that nothing was output. The debug found that when recursively entering the next layer of functions, it is the first The entry function is incremented by 1, so the values ​​of left and right are always 0.

Visible, when recursive, you cannot change the value of the variable at the layer.