[LeetCode] 22. Generate Parentheses

https://leetcode.com/

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

 

Example 2:

Input: n = 1
Output: ["()"]

 

Constraints:

• 1 <= n <= 8

 

Code :

var generateParenthesis = function(n) {
    // 괄호 조합을 저장할 배열을 선언합니다.
    const combinations = [];
    // DFS 탐색을 수행하는 함수를 선언합니다.
    const dfs = (left, right, combination) => {
        // 괄호 쌍의 개수가 주어진 n과 일치하면 현재 괄호 조합을 combinations 배열에 추가합니다.
        if (left === n && right === n) {
            combinations.push(combination);
            return;
        }
        // 왼쪽 괄호의 개수가 오른쪽 괄호의 개수보다 많은 경우에는 왼쪽 괄호와 오른쪽 괄호를 추가할 수 있습니다.
        if (left > right) {
            // 왼쪽 괄호의 개수가 n 미만인 경우에는 왼쪽 괄호를 추가합니다.
            left < n && dfs(left + 1, right, combination + '(');
            // 오른쪽 괄호의 개수가 n 미만인 경우에는 오른쪽 괄호를 추가합니다.
            right < n && dfs(left, right + 1, combination + ')');
        } 
        // 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같은 경우에는 왼쪽 괄호를 추가합니다.
        else if (left === right) {
            left < n && dfs(left + 1, right, combination + '(');
        }
    }
    // DFS 탐색을 시작합니다.
    dfs(0, 0, '');
    // 생성된 모든 올바른 괄호 조합을 반환합니다.
    return combinations;
};

 

Solutions Code :

var generateParenthesis = function(n) {
  // 괄호 조합을 저장할 배열을 선언합니다.
  const result = [];
  // 재귀적으로 괄호를 생성하는 함수를 정의합니다.
  const generateParentheses = (result, current, open, close, n) => {
    // 생성된 괄호 조합의 길이가 2n과 일치하는 경우에는 현재 조합을 결과 배열에 추가하고 종료합니다.
    if (current.length === 2 * n) {
      result.push(current);
      return;
    }
    // 여는 괄호의 개수가 n보다 작은 경우에는 여는 괄호를 추가합니다.
    if (open < n) {
      generateParentheses(result, current + '(', open + 1, close, n);
    }
    // 닫는 괄호의 개수가 여는 괄호의 개수보다 작은 경우에는 닫는 괄호를 추가합니다.
    if (close < open) {
      generateParentheses(result, current + ')', open, close + 1, n);
    }
  };
  // 괄호를 생성하는 재귀 함수를 호출합니다.
  generateParentheses(result, '', 0, 0, n);
  // 생성된 모든 올바른 괄호 조합을 반환합니다.
  return result;
};

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode