22. Generate Parentheses

문제

https://leetcode.com/problems/generate-parentheses/?envType=problem-list-v2&envId=dynamic-programming

풀이

해당 문제는 백트레킹 알고리즘을 적용해 풀 수 있다.

sol 함수에서 여는 괄호의 갯수가 n보다 작다면 여는 괄호를 추가한 문자열을 재귀 동작으로 함수를 호출하고, 다른 if문에서는 여는 괄호의 갯수가 닫는 괄호의 갯수보다 많을 경우 닫는 경우의 조합을 구하기 위해 닫는 괄호를 추가한 문자열을 함수 호출해준다.

코드

/**
 * @param {number} n
 * @return {string[]}
 */
const generateParenthesis = (n) => {
    const result = [];
    const sol = (str, op, cl) => {
        if(op === n && cl === n){
            result.push(str);
            return;
        }

        if(op < n){
            sol(str + "(", op + 1, cl);
        }
        if(op > cl){
            sol(str + ")", op, cl + 1);
        }
    }

    sol("", 0, 0);
    return result;
};