[리트코드] 22. Generate Parentheses - js

1. 문제

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

Generate Parentheses - LeetCode

2. 코드

이 문제는 백트래킹을 활용하는 문제다. 

백트래킹이란 모든 경우의 수를 전부 고려하여 답을 체크하는 방식으로, 할 수 있는 가장 깊이 들어갔다가 모든 경우의 수를 고려했거나 조건에 맞지 않으면 다시 회귀하는 알고리즘이다. DFS와는 비슷하지만 다르므로, 두 알고리즘의 차이점을 잘 이해해야 한다.

백트래킹은 경로를 찾아가는 도중에 해가 되지 않을 것 같은 경로가 갔다면 더 가지 않고 되돌아온다. 이를 가지치기라고 부른다. 불필요한 경로를 조기 차단하기 때문에 확인해야 하는 경로 수를 줄일 수 있다.

DFS은 완전 탐색을 기본으로 하는 그래프 순회 기법으로, 가능한 모든 경로를 탐색한다. 불필요한 경로를 사전에 차단하지 않아 자원 소모가 심하다.

 

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    
    let stack = [];
    let result = [];

    function backtrack(open, close){

        if(open === close && open === n) {
            result.push(stack.join(''));
            return;
        }

        if(open < n){
            stack.push('(');
            backtrack(open+1, close);
            stack.pop()
        }
        if(close < open){
            stack.push(')');
            backtrack(open, close+1);
            stack.pop();
        }

    }
    backtrack(0,0);
    
    return result;
};

open, close, stack, result 순으로 출력한 결과

<- ((( 시작
3 2 [ '(', '(', '(', ')', ')' ] [ '((()))' ] <- stack.pop()을 통해 마지막이였던 ')' 삭제
3 1 [ '(', '(', '(', ')' ] [ '((()))' ] 
3 0 [ '(', '(', '(' ] [ '((()))' ]
3 2 [ '(', '(', ')', '(', ')' ] [ '((()))', '(()())' ] <- (( 시작
3 1 [ '(', '(', ')', '(' ] [ '((()))', '(()())' ]
3 2 [ '(', '(', ')', ')', '(' ] [ '((()))', '(()())', '(())()' ]
2 2 [ '(', '(', ')', ')' ] [ '((()))', '(()())', '(())()' ]
2 1 [ '(', '(', ')' ] [ '((()))', '(()())', '(())()' ]
2 0 [ '(', '(' ] [ '((()))', '(()())', '(())()' ] <- ( 시작
3 2 [ '(', ')', '(', '(', ')' ] [ '((()))', '(()())', '(())()', '()(())' ]
3 1 [ '(', ')', '(', '(' ] [ '((()))', '(()())', '(())()', '()(())' ]
3 2 [ '(', ')', '(', ')', '(' ] [ '((()))', '(()())', '(())()', '()(())', '()()()' ]
2 2 [ '(', ')', '(', ')' ] [ '((()))', '(()())', '(())()', '()(())', '()()()' ]
2 1 [ '(', ')', '(' ] [ '((()))', '(()())', '(())()', '()(())', '()()()' ]
1 1 [ '(', ')' ] [ '((()))', '(()())', '(())()', '()(())', '()()()' ]
1 0 [ '(' ] [ '((()))', '(()())', '(())()', '()(())', '()()()' ]
0 0 [] [ '((()))', '(()())', '(())()', '()(())', '()()()' ]

 

참고한 글)

https://code-simple.tistory.com/7

[리트코드] 22. Generate Parentheses

https://sojeong-lululala.tistory.com/184

[이진탐색] 깊이 우선 탐색[DFS]과 백트래킹[Backtracking] 차이점