[leetcode] 22. Generate Parentheses

문제링크

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

input & output

Example 1

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

Example 2

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

---

Approach #1

// 알고리즘: backtracking
res = [];

3
((( )))
(() ())
(()) ()

( 여는 괄호가 n보다 작으면 ( 추가한다.
) 가  ( 보다 작으면 ) 추가한다.
string 길이가 n*2가 되면 string을 res에 push 


(-> (( -> ((( -> ((())) 
       -> (() -> (()( -> (()() -> (()())
              -> (()) -> (())( -> (())()
       
 -> () -> ()( -> ()(( -> ()(() -> ()(())
              -> ()() -> ()()( -> ()()()
       

Solution #1

var generateParenthesis = function(n) {
  const res = [];
  backtrack(res, "", 0, 0, n);
  return res;
  
};

function backtrack(res, curS, open, close, n){
  if(curS.length === n*2) res.push(curS);
  if(open<n) backtrack(res, curS+"(", open+1, close, n);
  if(close<open) backtrack(res, curS+")", open, close+1, n);
}

Time Complexity

O(2^2n)

처음 backtrack 함수에서 backtrack 재귀를 두번 호출하는데, 그 재귀에서 최종 문자가 나올때까지 계속 backtrack을 하기때문에 2^2n.
2n인 이유는 curS의 길이가 2N이 될때 재귀가 끝나기 때문.

Space Complexity

O(2n)

재귀함수에서 콜스택이 최대로 쌓였을때가 2n만큼이기 때문.

---

Solution #2

// time: O(2^2n) dfs 2번 도는데, 그걸 2n만큼,,,
// space: O(2n)
var generateParenthesis = function(n) {
    const res=[];
    let numS=0, numE=0;
    
    const dfs=(st,numS,numE)=>{
        if(numS<numE) return;
        if(numS > n) return;
        
        if(numE >= n){
            res.push(st);
            return;
        }
        
        dfs(st+"(",numS+1,numE); //st + "("할 때 시간복잡도 추가
        dfs(st+")",numS,numE+1); //st + ")"할 때 시간복잡도 추가
    }
    
    dfs("",numS,numE);
    
    return res;
};

Time Complexity

O(2^2n)

// st+ "(" 할때 시간복잡도 추가된다!
string에 문자 붙이는 것도 시간복잡도에 포함됨을 기억하자.

처음 dfs 함수에서 dfs 재귀를 두번 호출하는데, 그 재귀에서 최종 문자가 나올때까지(2n만큼) 계속 dfs함수 돌기 때문에 2^2n.

Space Complexity

O(2n)

재귀함수에서 콜스택이 최대로 쌓였을때가 2n만큼이기 때문.