drop-of-water

문제 링크

조건

  • 1 <= n <= 8

입력값

  • n = 괄호의 pair 갯수

출력값

  • 괄호짝이 맞는 combination을 배열에 넣어 출력

풀이과정

  • backtracking을 사용해 combination을 만든다
  • combination의 길이가 2*n인 경우 pair가 꽉 차있기 때문에 result에 결과를 넣어준다
  • 왼쪽 괄호가 아직 n 개 만큼 없는 경우 왼쪽 괄호를 넣어준다
  • 오른쪽 괄호가 아직 왼쪽 괄호의 갯수만큼 없다면 오른쪽 괄호를 넣어준다
  • 이렇게 하면 괄호짝이 맞는 well-formed combination을 완성할 수 있다

코드

var generateParenthesis = function (n) {
  let result = [];

  const dfs = (arr, left, right) => {
    // combination의 길이가 2*n인 경우 pair가
    // 꽉 차있기 때문에 result에 현재 array 값을 넣어준다
    if (arr.length == 2 * n) {
      result.push(Array.from(arr).join(''));
      return;
    }

    // 왼쪽 괄호가 아직 n 개 만큼 없는 경우
    // 왼쪽 괄호를 넣어준다
    if (left < n) {
      arr.push('(');
      dfs(arr, left + 1, right);
      arr.pop();
    }

    // 오른쪽 괄호가 아직 왼쪽 괄호의 갯수만큼
    // 없다면 오른쪽 괄호를 넣어준다
    if (right < left) {
      arr.push(')');
      dfs(arr, left, right + 1);
      arr.pop();
    }
  };

  dfs([], 0, 0);
  return result;
};

😊