数字 n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1 输出:["()"]
提示:
1 <= n <= 8
只有两种填充状态的回溯法应用,注意一下括号有效的性质可以剪枝。
1 class Solution 2 { 3 public: 4 vector<string> result; 5 void travel(int n, int left_number, int right_number, string now) 6 { 7 if (now.length() == n * 2) 8 { 9 result.push_back(now); 10 return; 11 } 12 if (left_number < n) 13 { 14 now.push_back('('); 15 travel(n, left_number + 1, right_number, now); 16 now.pop_back(); 17 } 18 if (left_number > right_number) 19 { // 左括号数大于右括号数时才能插入右括号 20 now.push_back(')'); 21 travel(n, left_number, right_number + 1, now); 22 now.pop_back(); 23 } 24 } 25 vector<string> generateParenthesis(int n) 26 { 27 string temp = ""; 28 travel(n, 0, 0, temp); 29 return result; 30 } 31 };