[LeetCode] 22. Generate Parentheses

문제

 

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: ["()"]

 

 

 

 

 

내 생각

 

문제 요약

주어진 'n' 의 괄호의 쌍을 조합하여 광호 조합을 생성하는 문제이다.

1. 여는 괄호'(' 의 개수와 닫는 괄호 ')'의 개수가 같다.

2. 닫는 괄호의 개수 < 여는 괄호의 개수

 

백트래킹을 이용한 풀이로 가능한 모든 조합을 탐색(괄호 조합)하면서 조건에 맞는 조합을 선택한다.

 

종료 조건 

• '('의 개수와 ')'의 개수가 n일 때 종료한다.

recurse 하는 부분은 괄호 조합을 하는 부분

• '(' 를 추가할 수 있는 경우: open > 0이면 '(' 를 추가하고 generate 호출
• ')' 를 추가할 수 있는 경우: close > open이면 ')' 를 추가하고 generate 호출

 

* 올바른 괄호인지 검사하는 문제는 스택을 이용했던거 같은데 , 올바른 괄호 조합을 생성하는 문제라 백트래킹을 사용하는 듯

 

 

내 코드

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        generate(result, "", n, n);
        return result;
    }

    // 괄호 조합(재귀)
    private void generate(List<String> result, String current, int open, int close) {
        // 남은 여는 괄호와 닫는 괄호의 수가 모두 0이 되면? -> 올바른 조합
        if (open == 0 && close == 0) {
            result.add(current);
            return;
        }

        // 여는 괄호를 추가할 수 있는 경우
        if (open > 0) {
            generate(result, current + "(", open - 1, close);
        }

        // 닫는 괄호를 추가할 수 있는 경우
        if (close > open) {
            generate(result, current + ")", open, close - 1);
        }
    }
}