数字 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("()()")