.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Medium
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Plain Text
복사
Example 2:
Input: n = 1
Output: ["()"]
Plain Text
복사
Constraints:
•
1 <= n <= 8
My solution
괄호가 조건에 맞게 조합되어야 한다.
그냥 괄호를 넣게 되면 열린 괄호가 나오기 전에 닫힌 괄호가 1개 이상 나오게 되고 필요없는 조합에 대한 연산을 하게 된다. 따라서 열린 괄호가 나왔다면 그 개수보다 닫힌 괄호의 개수가 더 작을 때만 닫힌 괄호가 나올 수 있는 조건문을 넣었다.
oL : DFS에서 열린 괄호를 추가해주었을 때 1만큼 depth가 늘어나는 것을 저장하고 있는 변수
cL : DFS에서 닫힌 괄호를 추가해주었을 때 1만큼 depth가 늘어나는 것을 저장하고 있는 변수
if (cL < oL) {
temp.push(')');
dfsParenthesis(oL, cL + 1);
temp.pop();
}
JavaScript
복사
그리고 닫힌 괄호와 열린 괄호는 n*2개가 나와야하고 각각이 절반씩 나와야 하는데, 닫힌 괄호의 개수에 대한 위의 조건이 있어서 열린 괄호에 대해서만 n개보다 적게 나왔을 때 더 나올 수 있도록 조건을 주었다.
if (oL < n) {
temp.push('(');
dfsParenthesis(oL + 1, cL);
temp.pop(); // 리턴되는 순간 배열에서 방금 사용한 괄호를 없애주어야 한칸 이전으로 갈 수 있음
}
JavaScript
복사
각각의 조건에서 괄호를 추가하는 것은 temp 배열에서 유지했다. 동일한 배열로 계속해서 사용하기 때문에 push해서 dfs 함수에 들어가게 되면 결국 temp.length가 M(n*2)과 같아지는 경우 완성된 temp를 얕은 복사해서 문자열로 연결한 다음(join()) comb 배열에 넣어준다. 그리고 다음에 실행되는 위의 조건문들은 실행되지 않지만 early return 시켜서 불필요한 연산을 방지했다.
if (temp.length === M) {
comb.push(temp.slice().join(''));
return;
}
JavaScript
복사
소스코드
/**
* @param {number} n
* @return {string[]}
*/
const generateParenthesis = function (n) {
const temp = [];
const comb = [];
const M = n * 2;
function dfsParenthesis(oL, cL) {
if (temp.length === M) {
comb.push(temp.slice().join(''));
return;
}
if (oL < n) {
temp.push('(');
dfsParenthesis(oL + 1, cL);
temp.pop(); // 리턴되는 순간 배열에서 방금 사용한 괄호를 없애주어야 한칸 이전으로 갈 수 있음
}
if (cL < oL) {
temp.push(')');
dfsParenthesis(oL, cL + 1);
temp.pop();
}
}
dfsParenthesis(0, 0);
return comb;
};
test('TC1', () => {
expect(generateParenthesis(3)).toStrictEqual(['((()))', '(()())', '(())()', '()(())', '()()()']);
});
test('TC2', () => {
expect(generateParenthesis(1)).toStrictEqual(['()']);
});
JavaScript
복사
