C++ 22. Generate Parentheses(Leet Code)

Leet Code_22. Generate Parentheses

Dynamic Programming

 

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

 

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

n개의 괄호를 표현할 수 있는 모든 경우의 수를 만들기

​

방법

1. n개의 괄호를 표현할 수 있는 모든 경우의 수를 만들기

 

결과

n개의 괄호를 표현할 수 있는 모든 경우의 수를 만들기

 

통과한 코드

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string>ans;
        int tail=0,left=n,right=n,k=0;
        string s(n*2, 'a');  
        dfs(tail,left,right,k,s,ans);
        return ans;
    }
    void dfs(int tail,int left,int right,int k,string& s,vector<string>& ans){
        if(left==0&&right==0){
            ans.push_back(s);
            return;
        }
        if(k==0){
            s[tail]='(';
            dfs(tail+1,left-1,right,k+1,s,ans);
            return;
        }
        else{
            if(left!=0){
                s[tail]='(';
                dfs(tail+1,left-1,right,k+1,s,ans);
            }
            if(right!=0){
                s[tail]=')';
                dfs(tail+1,left,right-1,k-1,s,ans);
            }
        }
        return;
    }
};

난이도를 Medium으로 올리면서 점점 시간이 걸린다

DP는 접근은 같지만 실제로 구현하기엔 아직 참 헷갈리는거 같다

머리속으로는 방법이 생각나는데 코드로 바로 나오지 않는다. 재귀라 참 헷갈리는듯..

문제만봐도 바로 풀수있을때까지 연습하자