LeetCode:22. 括号生成

 

题目:https://leetcode-cn.com/problems/generate-parentheses/submissions/

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

 

解题思路:

  1. 通过递归找到所有可能,也就是递归的公式,实现从大到小的缩小。
  2. 边界条件进行筛选,排除一些无效的可能;
  3. 将所有有效的结果全部push到动态数组当中;

边界条件注意:

左右括号都是一一对应,并且左括号先出现,再出现右括号(左括号数量大与右括号);

左右括号不能超过给定括号对数n;

 

这题比较新颖的地方是 将括号全部当中字符串,然后不断通过字符串相加,将一组括号当成一组字符串,这样操作字符串比较方便。

class Solution {
public:
    vector<string> generateParenthesis(int n) 
    { 
        std::vector<string> result;
        string item="";
        generate(item, n, n, result);
        return result;
    }

    void generate(std::string item, int letf, int right, std::vector<string> &result)
    {
        if (letf==0 && right==0)
        {
            result.push_back(item);
            return;
        }   
        if (letf > 0)
        {
            generate(item+'(', letf-1, right, result);
        }
        if (letf < right)
        {
            generate(item+')', letf, right-1, result);
        }
    }
};

 

上一篇:我要做CPU_3


下一篇:刷题22. Generate Parentheses