Generate Parentheses[String,Dynamic Programming,Backtracking]

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

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

 

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

 

Constraints:

• 1 <= n <= 8

간단한 Dynamic Programming 코딩 한 번 해보기!

문제는 쉬워 보이나, 막상 코딩하려니까 좀 짜친다.

 

 

1. Python

아래까지 풀다가 GG. 뭔가 뒤에 방법이 생각 안 난다.

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        dp = dict()
        for i in range(1,n+1):
            dp[i] = []
        dp[1] = ['()']
        for j in range(2,n+1):
            for x in dp[j-1]:
                dp[j].append('()'+x) 
            # '((' 로 시작하는 친구들을 더해야 하는데 어떻게 할까
            

        return dp[n]

 

일단, GPT에 힌트를 구해서 ㅠㅠ

Idea로 승부한 code를 짰는데, 성능은 좋지 않지만 그래도 pass는 했다.

 

골자는, dp[n] 을 만들 땐, dp[n-1]에서 만들어진 놈들을 불러와서 각 자리에 '( )'를 더해주는 것

 

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        dp = dict()
        for i in range(1,n+1):
            dp[i] = []
        dp[1] = ['()']
        for j in range(2,n+1):
            for x in dp[j-1]:
                for k in range(len(x)):
                    temp = x[:k]+'()'+x[k:]
                    if temp not in dp[j]:
                        dp[j].append(temp)
        return dp[n]

s= Solution()
print(s.generateParenthesis(1))
print(s.generateParenthesis(2))
print(s.generateParenthesis(3))
print(s.generateParenthesis(4))
['()']
['()()', '(())']
['()()()', '(())()', '()(())', '(()())', '((()))']
['()()()()', '(())()()', '()(())()', '()()(())', '(()())()', '((()))()', '(())(())', '()(()())', '()((()))', '(()()())', '((())())', '(()(()))', '((()()))', '(((())))']

 

좀 멋지게 Recursive하게 푸는 방법은 아래와 같다.

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def backtrack(i, j, path):
            if i == j == n:
                ans.append(''.join(path[:]))
                return 
            
            if i < n:
                path.append('(')
                backtrack(i + 1, j, path)
                path.pop()
            
            if j < i:
                path.append(')')
                backtrack(i, j + 1, path)
                path.pop()
            
        backtrack(0, 0, [])
        return ans

 

 

2. C++

DP / Recursive를 이용해보자

 

- DP (센스 있다 이거)

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<vector<string>> dp(n+1);
        dp[0] = {""};
        
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                for(const string left : dp[j]){
                    for(const string right : dp[i-j-1]){
                        dp[i].push_back("("+left+")"+right);
                    }
                }
            }
        }
        return dp[n];
    }
};

 

- Recursive

뇌 꼬인다.. 솔직히 이건 봐도 모르겠다.

 

Naive한 방법 -> 대충 알겠음 / DP -> 코드 보면 알겠음 / Recursive -> 코드 봐도 모르겠음

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        helper(ans,"",n,n);
        return ans;
    }
    
    void helper(vector<string>& ans,string curr, int l, int r){
        if(l==0 && r==0){
            ans.push_back(curr);
            return;
        }
        if(l>0) helper(ans,curr+"(",l-1,r);
        if(l<r) helper(ans,curr+")",l,r-1);

    }
};