数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

  1. 输入：n = 3
  2. 输出：[
  3.        "((()))",
  4.        "(()())",
  5.        "(())()",
  6.        "()(())",
  7.        "()()()"
  8.      ]

c plus

  • 递归

    1. /* 括号的判断条件：
    2. ** left <= n, n表示括号的个数
    3. ** right <= left
    4. */
    5. class Solution {
    6. public:
    7.   vector<string> res;
    8.   vector<string> generateParenthesis(int n) { 
    9.       generate(0, 0, n, "");
    10.       return res;
    11.   }
    12.   void generate(int left, int right, int n, string s) {
    13.       //终止
    14.       if (left == n && right == n) {
    15.           res.push_back(s);
    16.       }
    17.       //本层处理
    18.       if (left < n) generate(left + 1, right, n, s + "(");
    19.       //先走到底画完左括号，返回的时候left = 2 // left = 1，会执行下面的语句画右括号
    20.       if (right < left) generate(left, right + 1, n, s + ")");
    22.   }
    23. };

  • 递归，先画完整的括号

    1. class Solution {
    2. public:
    3.   vector<string> generateParenthesis(int n) {
    4.       vector<string> res;
    5.       addingpar(res, n, 0, "", );
    6.       return res;
    7.   }
    8.   void addingpar(vector<string>& v, int left, int right, string str){
    9.       if(left==0 && right==0) {
    10.           v.push_back(str);
    11.           return;
    12.       }
    13.       if(m > 0) addingpar(v, left, right - 1, str + ")"); 
    14.       if(n > 0) addingpar(v, left - 1, right + 1, str + "(");//画了一个左括号后就画右括号
    15.   }
    16. };

Golang

  • 练习
    1. var res []string
    2. func generateParenthesis(n int) []string {
    3.   res = make([]string, 0, n)
    4.   generate(0, 0, n, "")
    5.   return res
    6. }
    7. func generate(left int, right int, n int, s string) {
    8.   if left == n && right == n {
    9.     res = append(res, s)
    10.   }
    11.   if left < n {
    12.       generate(left + 1, right, n, s + "(")
    13.   }
    14.   if right < left {
    15.       generate(left, right + 1, n, s + ")")
    16.   }
    17. }

%3E%E6%95%B0%E5%AD%97%20n%20%E4%BB%A3%E8%A1%A8%E7%94%9F%E6%88%90%E6%8B%AC%E5%8F%B7%E7%9A%84%E5%AF%B9%E6%95%B0%EF%BC%8C%E8%AF%B7%E4%BD%A0%E8%AE%BE%E8%AE%A1%E4%B8%80%E4%B8%AA%E5%87%BD%E6%95%B0%EF%BC%8C%E7%94%A8%E4%BA%8E%E8%83%BD%E5%A4%9F%E7%94%9F%E6%88%90%E6%89%80%E6%9C%89%E5%8F%AF%E8%83%BD%E7%9A%84%E5%B9%B6%E4%B8%94%20%E6%9C%89%E6%95%88%E7%9A%84%20%E6%8B%AC%E5%8F%B7%E7%BB%84%E5%90%88%E3%80%82%0A%60%60%60%0A%E8%BE%93%E5%85%A5%EF%BC%9An%20%3D%203%0A%E8%BE%93%E5%87%BA%EF%BC%9A%5B%0A%20%20%20%20%20%20%20%22((()))%22%2C%0A%20%20%20%20%20%20%20%22(()())%22%2C%0A%20%20%20%20%20%20%20%22(())()%22%2C%0A%20%20%20%20%20%20%20%22()(())%22%2C%0A%20%20%20%20%20%20%20%22()()()%22%0A%20%20%20%20%20%5D%0A%60%60%60%0A%0A%0A%23%23%23%20c%20plus%0A%0A%0A%0A%20%E9%80%92%E5%BD%92%0A%60%60%60c%0A%2F*%20%E6%8B%AC%E5%8F%B7%E7%9A%84%E5%88%A4%E6%96%AD%E6%9D%A1%E4%BB%B6%EF%BC%9A%0A%20left%20%3C%3D%20n%2C%20n%E8%A1%A8%E7%A4%BA%E6%8B%AC%E5%8F%B7%E7%9A%84%E4%B8%AA%E6%95%B0%0A%20right%20%3C%3D%20left%0A%2F%0A%0Aclass%20Solution%20%7B%0Apublic%3A%0A%20%20%20%20vector%3Cstring%3E%20res%3B%0A%20%20%20%20vector%3Cstring%3E%20generateParenthesis(int%20n)%20%7B%20%0A%20%20%20%20%20%20%20%20generate(0%2C%200%2C%20n%2C%20%22%22)%3B%0A%20%20%20%20%20%20%20%20return%20res%3B%0A%20%20%20%20%7D%0A%0A%20%20%20%20void%20generate(int%20left%2C%20int%20right%2C%20int%20n%2C%20string%20s)%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%E7%BB%88%E6%AD%A2%0A%20%20%20%20%20%20%20%20if%20(left%20%3D%3D%20n%20%26%26%20right%20%3D%3D%20n)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20res.push_back(s)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%2F%2F%E6%9C%AC%E5%B1%82%E5%A4%84%E7%90%86%0A%20%20%20%20%20%20%20%20if%20(left%20%3C%20n)%20generate(left%20%2B%201%2C%20right%2C%20n%2C%20s%20%2B%20%22(%22)%3B%0A%20%20%20%20%20%20%20%20%2F%2F%E5%85%88%E8%B5%B0%E5%88%B0%E5%BA%95%E7%94%BB%E5%AE%8C%E5%B7%A6%E6%8B%AC%E5%8F%B7%EF%BC%8C%E8%BF%94%E5%9B%9E%E7%9A%84%E6%97%B6%E5%80%99left%20%3D%202%20%2F%2F%20left%20%3D%201%EF%BC%8C%E4%BC%9A%E6%89%A7%E8%A1%8C%E4%B8%8B%E9%9D%A2%E7%9A%84%E8%AF%AD%E5%8F%A5%E7%94%BB%E5%8F%B3%E6%8B%AC%E5%8F%B7%0A%20%20%20%20%20%20%20%20if%20(right%20%3C%20left)%20generate(left%2C%20right%20%2B%201%2C%20n%2C%20s%20%2B%20%22)%22)%3B%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20%7D%0A%7D%3B%0A%60%60%60%0A%20%E9%80%92%E5%BD%92%EF%BC%8C%E5%85%88%E7%94%BB%E5%AE%8C%E6%95%B4%E7%9A%84%E6%8B%AC%E5%8F%B7%0A%60%60%60c%0Aclass%20Solution%20%7B%0Apublic%3A%0A%20%20%20%20vector%3Cstring%3E%20generateParenthesis(int%20n)%20%7B%0A%20%20%20%20%20%20%20%20vector%3Cstring%3E%20res%3B%0A%20%20%20%20%20%20%20%20addingpar(res%2C%20n%2C%200%2C%20%22%22%2C%20)%3B%0A%20%20%20%20%20%20%20%20return%20res%3B%0A%20%20%20%20%7D%0A%20%20%20%20void%20addingpar(vector%3Cstring%3E%26%20v%2C%20int%20left%2C%20int%20right%2C%20string%20str)%7B%0A%20%20%20%20%20%20%20%20if(left%3D%3D0%20%26%26%20right%3D%3D0)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20v.push_back(str)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20if(m%20%3E%200)%20addingpar(v%2C%20left%2C%20right%20-%201%2C%20str%20%2B%20%22)%22)%3B%20%0A%20%20%20%20%20%20%20%20if(n%20%3E%200)%20addingpar(v%2C%20left%20-%201%2C%20right%20%2B%201%2C%20str%20%2B%20%22(%22)%3B%2F%2F%E7%94%BB%E4%BA%86%E4%B8%80%E4%B8%AA%E5%B7%A6%E6%8B%AC%E5%8F%B7%E5%90%8E%E5%B0%B1%E7%94%BB%E5%8F%B3%E6%8B%AC%E5%8F%B7%0A%20%20%20%20%7D%0A%7D%3B%0A%0A%60%60%60%0A%0A%0A%0A*%0A%0A%23%23%23%20Golang%0A%0A%0A%20%E7%BB%83%E4%B9%A0%0A%0A%60%60%60go%0Avar%20res%20%5B%5Dstring%0Afunc%20generateParenthesis(n%20int)%20%5B%5Dstring%20%7B%0A%20%20%20%20res%20%3D%20make(%5B%5Dstring%2C%200%2C%20n)%0A%20%20%20%20generate(0%2C%200%2C%20n%2C%20%22%22)%0A%20%20%20%20return%20res%0A%7D%0A%0Afunc%20generate(left%20int%2C%20right%20int%2C%20n%20int%2C%20s%20string)%20%7B%0A%20%20%20%20if%20left%20%3D%3D%20n%20%26%26%20right%20%3D%3D%20n%20%7B%0A%20%20%20%20%20%20res%20%3D%20append(res%2C%20s)%0A%20%20%20%20%7D%0A%0A%20%20%20%20if%20left%20%3C%20n%20%7B%0A%20%20%20%20%20%20%20%20generate(left%20%2B%201%2C%20right%2C%20n%2C%20s%20%2B%20%22(%22)%0A%20%20%20%20%7D%0A%20%20%20%20if%20right%20%3C%20left%20%7B%0A%20%20%20%20%20%20%20%20generate(left%2C%20right%20%2B%201%2C%20n%2C%20s%20%2B%20%22)%22)%0A%20%20%20%20%7D%0A%0A%7D%0A%60%60%60%0A%0A*