[Algorithm] 괄호 쌍 만들기

문제

괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 배열을 리턴하시오.

입출력 예

입력 출력
2 [”(())”, ”()()”]
3 [ ’((()))’, ’(()())’, ’(())()’, ’()(())’, ’()()()’ ]

풀이

재귀를 이용해 푼다. 각 쌍의 수는 매개변수 n과 일치할 것이므로, base case에서 괄호가 열리고 닫힌 횟수가 n과 일치할 때 완성한 괄호 문자열을 하나씩 넣어 준다.

나머지 재귀식에서는 괄호가 열리고 닫힐 때 문자열에 해당 상황에 맞는 괄호를 더해 준다.

function solution(n) {
  const result = [];
  function makeBracket(open = 0, close = 0, bracket = ''){

    if (open < close) return;
    
    if (close === n) {
      result.push(bracket)
      return;
    }

    if (open < n) {
      makeBracket(open + 1, close, bracket + '(')
    }

    if (close < n) {
      makeBracket(open, close + 1, bracket + '(')
    }
  }

  makeBracket();

  return result;
}
2019년 05월 11일 작성

대부분 제가 배운 것들을 남기기 위해 글을 쓰고 있습니다. 이 글이 도움이 된다면 매우 기쁘겠지만, 설명이 다소 불친절하거나 오류가 있다면 댓글 남겨주세요. 더 성장하는 기회가 될 거에요 :)

🚀 bob on Github