Написано: 28.02.2023

22. Генерировать скобки (Generate Parentheses)

medium

Задание.

Получено число n, обозначающее количество пар круглых скобок.

Нужно написать функцию для генерации всех комбинаций правильно сформированных круглых скобок.

Пример 1.

Входные данные: n = 3

Результат: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

Пример 2.

Входные данные: n = 1

Результат: [”()”]

Решение.

class Solution {
private:
    void helper(vector<string> &v, int n, int oc, int cc, string s)
    {
        if(oc == n && cc == n){
            v.push_back(s);
            return ;
        }
        if(oc<n) {
            helper(v, n, oc+1, cc, s+"(");
        }
        if(cc < oc) {
            helper(v, n, oc, cc+1, s+")");
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> v;
        int oc=0, cc=0;
        helper(v, n, oc, cc, "");
        return v;
    }
};