Generate Parentheses

🔗 문제 링크

https://leetcode.com/problems/generate-parentheses/

🔍 문제 설명

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

⚠️ 제한사항

• $1 <= n <= 8$

🗝 풀이 (언어 : Java)

백트래킹으로 푸는 문제이다. 백트래킹이 DFS를 이용해서 안되는 경우는 되돌아가서 다른 경우의 수를 체크하는 것이라 하는데, DFS와 차이를 모르겠다. 이 문제는 괄호의 개수 제한을 넘지 않는 것, 그리고 여는 괄호의 사용 수가 닫는 괄호의 사용 수보다 항상 많거나 같아야 한다는 점을 주의해야 한다.

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

class Solution {
    private void dfs(List<String> answer, int open, int close, String str) {
        // 괄호 개수 제한을 넘어가거나, 여는 괄호보다 닫는 괄호의 남은 수가 더 많을 경우 탈락
        if (open < 0 || open > close)
            return;
        // 정답 체크
        if (open == 0 && close == 0) {
            answer.add(str);
            return;
        }
        // 여는 괄호, 닫는 괄호 경우의 수 모두 DFS
        dfs(answer, open-1, close, str+"(");
        dfs(answer, open, close-1, str+")");
    }

    public List<String> generateParenthesis(int n) {
        List<String> answer = new ArrayList<>();
        // 올바른 괄호가 되려면 무조건 시작은 여는 괄호로 시작해야 한다
        dfs(answer, n-1, n, "(");
        return answer;
    }
}