LeetCode : 22. Generate Parentheses

backtracking을 연습하기에 매우 좋은, 지저분하지 않고 간단 명료한 문제!

 

()와 같은 열고 닫는 괄호를 통해 굉장히 많은 문제가 출제될 수 있는데, 대표적인 것이

이 문제와 같이 열고닫는 괄호(올바른 괄호)의 조합을 찾는 문제, 올바른 괄호인지 아닌 지의 여부를 묻는 문제, 괄호의 쌍을 묻는 문제 등등....

 

[메인 로직]

open, close와 같은 변수로 현재 문자열에 몇개의 여는 괄호와 닫는 괄호가 있는 지 표시해주었고

open<=n까지 추가할 수 있도록, close는 close의 개수만큼 추가할 수 있도록 로직을 구현했다.

아무래도 코드를 참고하시는 것이 더 이해가 빠를 것이라 생각된다.

 

class Solution {
public:
    vector<string> ans;
    int N;
    void dfs(int open, int close, string s){
        if(open==N){
            for(int i=0; i<close; i++){
                s += ')';
            }
            ans.push_back(s);
            return;
        }
        
        dfs(open+1, close+1, s+'(');
        if(close>0){
            dfs(open, close-1, s+')');
        }
    }
    
    vector<string> generateParenthesis(int n) {
        N = n;
        dfs(0, 0, "");
        
        return ans;
    }
};