LeetCode Generate Parentheses (JavaScript)

링크 : 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

---

문제 풀이

dfs를 활용해 문제 해결

dfs의 인자로 빈문자열, n(개의 여는괄호), n(개의 닫는괄호) 를 전달 받음

1. left가 0이라는 건 여는 괄호를 모두 사용했으므로 answer에 만들어진 괄호 형태 저장 (right는 남아있을 수 있으므로 right가 0보다 크다면 ')'를 붙여줌)

2. left가 0이 아니라면 str에 '('를 붙여주고 left - 1로 재귀

3. right가 0이 아니라면 str에 ')'를 붙여주고 right -1로 재귀. 단, 올바른 괄호를 만들기 위해 right - 1를 한 값이 left보다 크거나 같아야함 (left보다 작다면 올바르지 않은 괄호 형태임)

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const answer = [];

    const dfs = (str, left, right) => {
        if (left === 0) {
            return answer.push(str + ')'.repeat(right));
        }

        if (left !== 0) {
            dfs(str + "(", left - 1, right);
        }

        if (right !== 0 && left <= right - 1) {
            dfs(str + ")", left, right - 1);
        }
    }

    dfs('', n, n);

    return answer;
};

---

결론

stack자료구조, dfs알고리즘을 이용하여 풀이