[LeetCode- Ch9. 백트래킹] 1. 생성된 괄호 #

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

Generate Parentheses - LeetCode

 

1. 특정 조건에서 반대로 돌 수 있도록 조건 생성

2. left와 right 모두 소진시 리스트에 넣는다.

 

class Solution {
    static int count=0;
    public List<String> generateParenthesis(int n) {
        //완성된 괄호의 개수가 n개인 가능한 조합을 모두 나열하라
        //여는 괄호가 n개일 때, n-1개일 때, n-2개일 때 ... -> n-i가 1개가 될때까지
        //3개 묶음,2개를 1개에 묶음, 2개묶음 1개묶음, 1개묶음 2개묶음, 1개 묶음 1개묶음 1개묶음
        //n+n-1개가 존재한다.
        //n==3
        //여는괄호 1개 -> 2개 
        //여는괄호 2개 -> 2개
        //여는괄호 3개 -> 1개
        
        //n==2
        //여는괄호 1개 -> 1개
        //여는괄호 2개 -> 1개
        
        //n==1
        //여는괄호 1개 -> 1개
        
        //=4C1 + 3C1
        //=3C1 + 2C1
        //=1C1 + 0
        
        //깊이 우선 탐색 DFS를 이용하는데, 
        //백트래킹을 이용한 조건탐색
        //: 주어진 (n,n)에서 시작해 open은 + close는 -로 대치해서, (-1, X)이 되면, 반대로 시작
        //: 즉, left가 0보다 작으면 right 시작
        
        List<String> result =new ArrayList<>();
        DFS(result, "", n,n,"");
        return result;
    }
    private void DFS(List<String> result, String str, int left, int right, String tmpstr){
        //1. 조건
        count++;
        System.out.println("str\t"+str+"\t left: "+left+" right:"+right+" count: "+count+" str1: "+tmpstr);
        if(left<0 || left>right) {
         return ;
        }
        //2. 반복 시작
        if(left==0 && right==0){
            result.add(str);
            return;
        }
        //추가
        DFS(result, str+'(',left-1, right, tmpstr+"+" );
        DFS(result, str+')', left, right-1, tmpstr+"-");
        
    }
}