Generate Parentheses (Medium)

문제

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

 

---

풀이

dp를 이용해서 전에 썼던 배열에 추가하기.

 

우선 dp 배열을 []로 초기화 하자

그리고 dp[0]에 빈 문자열 "" 추가

let dp = new Array(n + 1).fill(0).map(() => []);
dp[0].push("");

 

 

그런 다음 n-1 들의 조합에 ()를 더해주자.

 

ex) n =4

 dp[0] 와 dp[3] 

 dp[1] 와 dp[2]

 dp[2] 와 dp[1]

 dp[3] 와 dp[0]

의 조합

---

답안

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
    // dp 배열 []로 초기화
    let dp = new Array(n + 1).fill(0).map(() => []);

    // dp[0] 첫 배열에 빈 문자열 "" 추가 
    dp[0].push("");

    for (let i = 1; i <= n; i++) {
        for (let p = 0; p < i; p++) {
            let q = i - 1 - p;

            for (let left of dp[p]) {
                for (let right of dp[q]) {
                    dp[i].push(`(${left})${right}`);
                }
            }
        }
    }
    return dp[n];
};