[JavaScript] 22. Generate Parentheses 풀이과정 쉬운 설명 - backtrack, recursion 활용

22. Generate Parentheses - Mideum

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

 

문제 설명

문제 해결 전략

1. 우선 n값이 3이면 "(" 개수와 ")"개수가 각각 3개씩 총 6개 이어야 합니다. 

 

2. 하지만 갯수만 매치시켜서 찾을 경우 ")))(((" 이런 패턴에도 통과시키기 때문에, 이런 걸 걸러낼 필터가 필요합니다. 

 

3. 그리고 valid한 괄호들 모든 경우에 수를 리턴해야 합니다. 

 

 

구현 전략

 

1. 우선 valid한 괄호를 만들기 위해서는 기본적으로 양끝은 "(           )" 이렇게 끝나야 합니다. 

 

2. 그럼 다음으로, 양끝 괄호는 "(           )" 로 끝나되, 안을 어떻게 채울 것이냐에 따라 경우에 수가 달라집니다.

 

3. 일단 "("의 갯수를 open으로 카운트를 지정하고, ")"를 close로 지정합니다. 

 

4. valid한 괄호 패턴을 만들기 위해서 룰을 고민해보니 두 가지가 있었습니다. 

1. close의 갯수는 open을 넘을수없다. open > close 왜냐하면 매치되는 open이없어 invalid 괄호가 될수밖에없어서
()')'() -> invalid
open 갯수: 2
close 갯수: 3


2. close와 open갯수는 같아야한다. 
(()) -> valid
open 갯수: 2
close 갯수: 2

5. 1번룰을 이용하면 다음과 같은 결론을 내릴 수 있습니다. close 괄호는 open개수가 close 개수보다 많을 때만, 추가해줄 수 있다는 것입니다. 

 

6. 위 룰을 이용해 n = 3일때 나올 수 있는 경우에 수를 그려보겠습니다. 

정답

위와같이 경우의 수들을 모두 접근해 주기 위해서는 backtracking을 이용하여 풀어주어야 합니다. 

 

backtracking이란?

 

우리가 미로찾기를 할 때 탈출구를 찾는 방법과 같습니다. backtracking에 대하여 자세한 설명은 아래 유튜브 영상을 참고해주세요. 

요점만 이야기하자면, backtrack은 recursion을 이용해서 모든 경우의 수를 접근하는 알고리즘입니다. 

 

 

이때 backtrack을 코드로 구현할때 특징이 있습니다.

 

우리가 backtrack으로 미로 탈출구를 찾는다고 가정해봅시다.

 

 

어떤 코드도, "내가 벽을 마주했을때는 뒤로 되돌아가라"라고 말하지 않습니다. 

 

이 부분이 backtrack을 이해할때 가장 어려운 부분인 것 같습니다. 

 

 

그럼 우리가 풀던 이 문제와 미로 찾기가 무슨 연관인가 생각이 들수있습니다. 

 

미로 찾기에서는 벽을 마주하면, 다시 탈출구를 찾기 위해 이전 포지션에서 갈래길로 돌아갑니다. 이문제에서는 close의 개수가 open개수보다 많으면 그전 포지션으로 가게 합니다.

 

그리고 쌍의 갯수가 3개이면 3개와 match 할 때, 우리가 반환할 result에 string값으로 push 해줍니다.  

 

var generateParenthesis = function(n) {
    const result = [];
    generate([], 0, 0); //recursion실행
    return result;
    
   
    function generate(A, left, right) {
        
        //추가될 parantheses
        if (A.length === 2 * n) { // n 은 괄호 쌍의 갯수,
            //만약 Aarray가 쌍갯수와 같아지면 
            result.push(A.join(''));//결과에 추가될때 결과가 추가되며 recursion끝  
            console.log("join")
            return;
        }
        if (left < n) { //만약 ( 갯수가 n보다 작으면
        	A.push('(');
            console.log("result1"+ A)
            generate(A, left + 1, right); // "("가 추가되고 left 카운트가 +1이 된후 다시 recursion시작
            console.log("pop1" + A.pop()); //pop을 해주는 이유는, backtrack에서 다시 돌아가는 역할
           
        }
        if (right < left) { //만약 )갯수가 (보다 작으면 
        	A.push(')')
            console.log("result2"+ A)
            generate(A, left, right + 1);
            console.log("pop2" + A.pop()); 
        }
    }
    
};

 

이해를 돕기위해 로그를 통해 값이 어떻게 만들어지는지 확인해보겠습니다.

 

input: n=3

result1(
result1(,(
result1(,(,(
result2(,(,(,)
result2(,(,(,),)
result2(,(,(,),),)
join
pop2)
pop2)
pop2)
pop1(
result2(,(,)
result1(,(,),(
result2(,(,),(,)
result2(,(,),(,),)
join
pop2)
pop2)
pop1(
result2(,(,),)
result1(,(,),),(
result2(,(,),),(,)
join
pop2)
pop1(
pop2)
pop2)
pop1(
result2(,)
result1(,),(
result1(,),(,(
result2(,),(,(,)
result2(,),(,(,),)
join
pop2)
pop2)
pop1(
result2(,),(,)
result1(,),(,),(
result2(,),(,),(,)
join
pop2)
pop1(
pop2)
pop1(
pop2)
pop1(