LeetCode 22 - Generate Parentheses (Medium)

문제

LeetCode - 22번

풀이 과정

주어진 괄호쌍의 개수에 맞는 올바른 괄호 배치를 생성하는 백트래킹 문제입니다.

이때 해당 괄호배치가 올바르게 위해서는 양 끝의 괄호가 각각 ( 와 ) 여야 한다는 점을 유의하도록 합니다.
또한 괄호쌍이 올바르기 위해서는 ( 가 존재하지 않늦데 ) 가 ( 보다 먼저 할당되면 안됩니다.
따라서 각각의 재귀 호출마다 ( 의 여유분이 있다면 ) 를 시도해보는 방식으로 진행하였습니다.
다만 ( 또한 최대 n 번 만큼만 등장할 수 있으므로 left 와 leftCount 를 각각 구분하여
전자는 ( 의 여유분으로 ) 가 등장할때마다 감소시켜줬고, 후자는 현재까지 선택된 ( 의 개수를 나타내도록 하였습니다.

코드

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

  function dfs(parentheses, left, leftSelected, depth) {
    if (depth === 2 * n - 1) {
      answer.push(parentheses + ")");
      return;
    }

    // 만약 왼쪽 괄호가 존재한다면
    if (left) {
      dfs(parentheses + ")", left - 1, leftSelected, depth + 1);
    }

    // 왼쪽 괄호 여유분이 있다면
    if (leftSelected < n) {
      dfs(parentheses + "(", left + 1, leftSelected + 1, depth + 1);
    }
  }

  dfs("(", 1, 1, 1);
  return answer;
};