括号生成

给定一个整数 n，生成所有由 n 对括号组成的有效括号组合。

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]

这题也是一样的思路，但是要注意的是，要保证左括号的数量大于右括号的数量，否则就是无效的括号组合。这一点很重要，否则程序会超出预期。 提供枚举选哪个的思路：

1. 左括号的数量大于右括号的数量，才能选右括号。
2. 左括号的数量小于n，才能选左括号。
3. 左括号数量+右括号数量等于2n，才能输出。

class Solution {
public:
  vector<string> generateParenthesis(int n) {
    string temp ="";
    vector<string> res;
    int m = 2*n;
    function<void(int,int)> dfs =[&](int i,int j){//i是左括号数量，j是右括号数量
      //递归出口
      if( (i+j) == m){
        res.emplace_back(temp);
        return;
      }
      if(i<n){//左括号数量小于n，才能选左括号
        temp +="(";
        dfs(i+1,j);
        temp.pop_back();
      }

      if(j <i ){//左括号的数量大于右括号的数量，才能选右括号
        temp += ")";
        dfs(i,j+1);
        temp.pop_back();
      }

    };
    dfs(0,0);
    return res;
  }
};
:::

更新日志

2024/12/15 12:44

查看所有更新日志

• 64700-update leetcode于 2024/12/15