LeetCode 22. Сгенерировать круглые скобки
Для заданных n пар круглых скобок напишите функцию для генерации всех комбинаций правильных скобок.
Например при n = 3 набор решений:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
Я не совсем уверен, что не так с моим приведенным ниже кодом. Я использую dfs для создания всех комбинаций хорошо сформированных скобок, и я делаю это, отслеживая количество оставшихся левых скобок и количество оставшихся правых скобок. Однако количество оставшихся скобок изменится после того, как я вернусь из рекурсивного вызова, что приведет к появлению дополнительных скобок.
vector<string> generateParentheses(int n) {
vector<string> result;
dfs(result, "", n, n);
return result;
}
void dfs(vector<string> &result, string s, int num_left, int num_right){
if(num_left == 0 && num_right == 0){
result.push_back(s);
}
if(num_left > 0){
dfs(result, s += "(", num_left - 1, num_right);
}
if(num_right > 0 && num_right > num_left){
dfs(result, s += ")", num_left, num_right - 1);
}
}