[string & dfs] 22. Generate Parentheses

문제

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

예시

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

Example 2:

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

제약

• 1 <= n <= 8

코드

const generateParenthesis = (n) => {
    const combinations = [];
    
    const dfs = (left, right, combination) => {
        if (left === n && right === n) {
            combinations.push(combination);
            return;
        }
        
        if (left > right) {
            left < n && dfs(left + 1, right, combination + '(');
            right < n && dfs(left, right + 1, combination + ')');
        } else if (left === right) {
            left < n && dfs(left + 1, right, combination + '(');
        }
    }
    
    dfs(0, 0, '');
    return combinations;
};

풀이

• dfs를 활용하여 문제를 풀었다.
• 왼쪽 괄호 갯수(left), 오른쪽 괄호 갯수(right), 축적된 괄호 조합(combination) 을 인자로 하는 dfs 함수를 생성한다.
• 탈출조건으로는 왼쪽 괄호 갯수(left), 오른쪽 괄호 갯수(right)가 각각 n 이 될 때 combinations에 여태까지 축적시킨 괄호 조합을 push한다.
• 이외의 경우, left === right 일 때 왼쪽 괄호를 한개 추가하여 재귀를 진행한다.
• left > right 일 때는 왼쪽 1개를 추가하여 재귀를 진행하고 오른쪽 1개를 추가하여 재귀를 분산하여 진행한다.