括号对的生成

男娘i 2021-12-17 01:07 251阅读 0赞

题目描述：来源：[https://leetcode-cn.com/problems/generate-parentheses/][https_leetcode-cn.com_problems_generate-parentheses]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjQ3NTQ0_size_16_color_FFFFFF_t_70][]

解决方法：回溯法（c++实现）

主要思路利用这个问题的隐含的条件，在括号生成的任何时刻左括号的数量总是大于等于右括号的数量，先判断左括号的数量是否加到最大了，如果没有就继续记啊左括号，如果最大了开始加右括号，直到总的括号数为n的2倍。当一一种方法加完后，就回到之前左括号还没加到最大的时候，这时开始加右括号，相当于根据左括号的数量进行回溯，一层层的左括号的数量逐渐减少。

class Solution {
    public:
        int left=0,right=0;
        vector<string> res;
        void back(string temp,int n)
        {
            if(temp.length()==2*n)
            {
                res.push_back(temp);
                return ;
            }
            else
            {
                if(left<n)
                {
                    temp.push_back('(');
                    left++;
                    back(temp,n);
                    left--;
                    temp.pop_back();
                }
                if(right<n&&left>right)
                {
                    temp.push_back(')');
                    right++;
                    back(temp,n);
                    right--;
                    temp.pop_back();
                }
            }
        }
        
        vector<string> generateParenthesis(int n) {
           back("",n);
            return res;
        }
    };

[https_leetcode-cn.com_problems_generate-parentheses]: https://leetcode-cn.com/problems/generate-parentheses/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjQ3NTQ0_size_16_color_FFFFFF_t_70]: /images/20211214/13a34588dd7341caae09c6cb7059b251.png