반응형

[LeetCode, 리트코드] Generate Parentheses

반응형

1. Problem

 

음이 아닌 정수 n이 주어질 때, 모든 '(' 와 ')' 로 이루어진 유효한 조합들을 찾아라.


n= 3일 때는

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]


2. Solution

 

DFS를 이용하는 문제다. left와 right에 할당되는 값들을 정해주고 그걸 통해 조합을 찾는 코드다.


3. Code

class Solution {
    
public:
    vector<string> generateParenthesis(int n) {
        if(n == 0)
            return vector<string>();

        vector<string> result;

        generate(result, "", n, n);
        return result;
    }
    
    void generate(vector<string>& result, string s, int left, int right){
        if(left > right)
            return;
        
        if(left ==0 && right == 0){
            result.push_back(s);
            return;
        }
        
        if(left > 0){
            generate(result, s + "(", left-1, right);
        }
        if(right > 0) {
            generate(result, s + ")", left, right-1);
        }
    }
};


 


반응형

이 글을 공유하기

댓글

Designed by JB FACTORY