[LeetCode] 22. Generate Parentheses (C++)

문제

n개의 괄호쌍이 주어졌을 때 가능한 모든 조합

생각할 것

재귀를 사용해야할 것이다.

올바른 괄호의 조건을 생각해보기

1. 여는 괄호가 n개여야 한다.
2. 닫는 괄호는 열려있는 괄호보다 많으면 안된다. 먼저 열고나서 닫아줘야 한다.

코드

class Solution {
public:
    vector<string> res;
    void dfs(int open, int close, int n, string str){
        if(str.size() == n * 2){
            res.push_back(str);
            return;
        }

        if(open < n) dfs(open+1, close, n, str + "(");
        if(close < open) dfs(open, close+1, n, str + ")");
    }

    vector<string> generateParenthesis(int n) {
        dfs(0, 0, n, "");
        return res;
    }
};