[stack][Medium] 22. Generate Parentheses

https://leetcode.com/problems/generate-parentheses/description/

 

n의 개수에 해당하는 유효한 괄호 구조를 만들라.

 

특정 조건에 따라 더해 나갈 수 있는 조건을 제한하며 특정 길이까지 수행한다. 

stack 보다는 backtrack에 가깝다. 

 

진행 : '(' 를 더하거나 ')' 를 더할 수 있다.

조건 :

 1. open의 수가 n 보다 작으면 '('를 더할 수 있다. 

 2. open수가 close수보다 많을 때만, ')'를 더할 수 있다. 

 

완료 : string 길이가 nx2가 되면 완료 된다.

 

 

코드 

void BuildParenthesis(vector<string>& vBuff, string cur, int open, int close, int n)
{
    if (cur.size() == n * 2)
    {
        vBuff.push_back(cur);
        return;
    }

    if (open < n)
    {
        cur += "(";
        BuildParenthesis(vBuff, cur, open+1, close, n);
        cur.pop_back();
    }

    if(open > close)
    {
        cur += ")";
        BuildParenthesis(vBuff, cur, open, close+1, n);
        cur.pop_back();
    }
}

vector<string> generateParenthesis(int n) 
{
    vector<string> vRet;
    BuildParenthesis(vRet, "(", 1, 0, n);
    return vRet;
}

 

결과