22. Generate Parentheses

문제링크: https://leetcode.com/problems/generate-parentheses/

Solution

Recursion

만약 현재 '(': a개, ')': b개, 현재 결과 "????"라고 하면 이를

• '(': a - 1개, ')': b + 1개, 결과 "????("
• '(': a개, ')': b - 1개, 결과 "????)"

의 결과를 찾는 같은 문제로 바꿀 수 있다. 이를 점화식으로 생각하고 초기조건은 (n개, 탈출조건은 (, )가 모두 0개 일 경우의 결과로 정하면 재귀함수를 만들 수 있다.

Algorithm

• result를 결과를 담을 클로저의 자유변수로 선언한다.
• dfs함수는 백트래킹으로 현재 변수를 바탕으로 가능한 결과를 result에 담는 함수다.
• 위의 탈출조건을 바탕으로 모든 괄호를 사용하면 결과에 추가한다.
• 괄호 수가 음수면 더이상 탐색하지 않는다.
• 위의 점화식을 바탕으로 dfs재귀함수로 문제를 진행한다.
• dfs함수에 초기조건을 삽입하면 결과가 result에 추가되고 모든 결과를 반환한다.

var generateParenthesis = function(n) {
  // dfs
  const result = [];
  const dfs = (leftCount, rightCount, curResult) => { 
    if (leftCount === 0 && rightCount === 0) result.push(curResult);
    if (leftCount < 0 || rightCount < 0) return;
    dfs(leftCount - 1, rightCount + 1, curResult + '(');
    dfs(leftCount, rightCount - 1, curResult + ')');
  }
  dfs(n, 0, '');
  return result;
};