[Leetcode] 22. Generate Parentheses - java

문제 LINK

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

Generate Parentheses - LeetCode

Parentheses (괄호) 생성하기

( ) 를 n개를 생성하는 프로그램 짜기

풀이

접근 : 재귀 - 백트래킹

현재 상태에서 가능한 것들을 찾아서 char 배열에 저장함.
n개를 만들어야 하므로, char 배열 및 탐색의 깊이는 n * 2 (괄호 쌍 : '( )' ) 로 정하였다.

'(' = left
')' = right

왼쪽 괄호의 경우 초기 n개 초과일 경우엔 정상적으로 다 닫아준다고 가정할 시 n개 초과의 괄호가 생성 되지 못하게.
오른쪽 괄호의 경우 왼쪽 괄호 없이는 완벽한 '()' 형태로 만들 수 없기에 왼쪽 괄호보다 더 많은 오른쪽 괄호를 만들 지 못하다게 조건을 걸어주고 depth 까지 탐색하여 결과값을 저장함.

class Solution {
    static List<String> ans;
    public List<String> generateParenthesis(int n) {
        ans = new ArrayList<String>();

        generateParentheses(n*2, 0, 0, 0, new char[n*2]);
        return ans;
    }

    public void generateParentheses(int n, int depth, int left, int right, char [] g){

            if(n==depth){
                ans.add(String.valueOf(g));
                return ;
            }

            if(left<n/2){
                g[depth] = '(';
                generateParentheses(n, depth+1, left+1, right, g);
            }

            if(left>right){
                g[depth] = ')';
                generateParentheses(n, depth+1, left, right+1, g);
            }


    }
}