22. Generate Parentheses 문제의 자바 해결 방법: 효율적인 알고리즘

문제

Problem_Link

문제해결방법

• all combinations 조합 = 대부분의 경우, 재귀함수 DFS
• 반드시 ( 가 open한 다음 ) close 해야함 (조건에 맞는 조합만=백트래킹 알고리즘)
  • if(open<length)
  • if(close<open)
• n의 두배가 되면 끝 base case

시간복잡도: O((2^n) / 2), 공간복잡도: O((2^n) / 2)

https://github.com/eunhanlee/leetcode_22.GenerateParentheses/blob/master/README.md

import java.util.ArrayList;
import java.util.List;

/**
 * 주어진 n쌍의 괄호에서 올바른 괄호 조합을 모두 생성하는 클래스입니다.
 */
public class Solution {
    /**
     * 올바른 괄호 조합을 모두 생성합니다.
     *
     * @param n 괄호 쌍의 수
     * @return 올바른 괄호 조합의 리스트
     */
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, "", 0, 0, n);
        return result;
    }

    /**
     * 재귀적으로 올바른 괄호 조합을 모두 생성합니다.
     *
     * @param result 생성된 괄호 조합들의 리스트
     * @param currentString 현재까지 생성된 문자열
     * @param open 현재까지 열린 괄호의 수
     * @param close 현재까지 닫힌 괄호의 수
     * @param len 괄호 쌍의 수
     */
    private void backtrack(List<String> result, String currentString, int open, int close, int len) {
        if (currentString.length() == len * 2) {
            result.add(currentString);
            return;
        }

        if (open < len) {
            backtrack(result, currentString + "(", open + 1, close, len);
        }
        if (close < open) {
            backtrack(result, currentString + ")", open, close + 1, len);
        }
    }
}

설명

• 모든 컴비네이션은 2^n이고, 이는 백트래킹 알고리즘으로 절반이 삭제됨. (2^n) / 2
• 이를 정리하면 O(4^n/sqrt(n)) 와 같음.