力扣22. 括号生成

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

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

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

回溯法：

class Solution {
public:vector<string> ret;string s;//存储某一个组合//left:剩余的左括号数量//right:剩余的右括号数量void dfs(int left,int right,string& s){if(!left&&!right){ret.push_back(s);return;}if(left){s.push_back('(');dfs(left-1,right,s);s.pop_back();}if(right&&left<right){s.push_back(')');dfs(left,right-1,s);s.pop_back();}}vector<string> generateParenthesis(int n) {dfs(n,n,s);return ret;}
};

执行顺序：

dfs(2, 2, "")  // 初始调用
├── dfs(1, 2, "(")  // 选择左括号
│   ├── dfs(0, 2, "((")  // 选择左括号
│   │   ├── dfs(0, 1, "(()")  // 选择右括号
│   │   │   ├── dfs(0, 0, "(())")  // 选择右括号
│   │   │   │   ├── ret.push_back("(())")  // 保存结果
│   │   │   │   └── 回溯: s.pop_back()  // s = "(()"
│   │   │   └── 回溯: s.pop_back()  // s = "(("
│   │   └── 回溯: s.pop_back()  // s = "("
│   ├── dfs(1, 1, "()")  // 选择右括号
│   │   ├── dfs(0, 1, "()(")  // 选择左括号
│   │   │   ├── dfs(0, 0, "()()")  // 选择右括号
│   │   │   │   ├── ret.push_back("()()")  // 保存结果
│   │   │   │   └── 回溯: s.pop_back()  // s = "()("
│   │   │   └── 回溯: s.pop_back()  // s = "()"
│   │   └── 回溯: s.pop_back()  // s = "("
│   └── 回溯: s.pop_back()  // s = ""
└── // dfs(2, 1, ")") - invalid，不执行

                      dfs(2, 2, "")/                \dfs(1, 2, "(")       // dfs(2, 1, ")") - invalid，因为左括号数量不能大于右括号数量/           \dfs(0, 2, "((")    dfs(1, 1, "()")|                      |dfs(0, 1, "(()")  dfs(0, 1, "()(")|                      |
dfs(0, 0, "(())")  dfs(0, 0, "()()")|                      |
ret.push_back("(())")  ret.push_back("()()")