[JS] Generate Parentheses

🔒 문제 (LeetCode 22)

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

Constraints:

• 1 <= n <= 8

 

🌊 입출력

Example 1:

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

Example 2:

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

 

---

 

🔑 해결

🌌 알고리즘 - DFS

양쪽 괄호의 개수가 n으로 같아야 하고 올바른 괄호가 되려면 ' ( ' 의 개수가 ' ) ' 개수보다 항상 적어야 함

사용해야 하는 괄호를 n에서부터 하나씩 감소시키며 조합을 찾는다

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const result = []
    
    const dfs = (str, l, r) => {
        if(l > r) return
        
        if(l === 0 && r === 0) {
            result.push(str)
            return
        }
        
        if(l > 0) dfs(str + '(', l - 1, r)
        if(r > 0) dfs(str + ')', l, r - 1)     
    }
    
    dfs('', n, n)
    
    return result
};