[백트래킹] leetCode - Generate Parentheses

백트래킹 

 

재귀(recursion) 과 거의 동일하게 풀었다.

재귀와 거의 다를게 없다고 생각.

 

먼저 문제를 봐보자

 

 

문제 요약 - 먼저 int n 이 주어지고,

() 괄호의 정합성이 항상 맞으면서 n 만큼의 () 이 나오는 모든 경우를 표현하는 문제

 

 

문제 풀이 - 괄호 '(' 부분과 ')' 부분을 재귀 호출을 하고 ,

호출을 끝낼 수 있게 termination check 를 해준다.

 

코드에서 (open < n && close < n) 이 termination check 를 해준 부분이고,

먼저 괄호 ( 가 n 번 만큼 나오게 재귀 호출을 해준후 

다시 ( 가 나온 만큼 ')' 가 호출 되도록 재귀 호출을 해준다.

이렇게 하면 open 이 n 번 만큼 close가 n 번만큼 나오는 모든 경우의 수를 볼 수 있다.

 

코드 - https://github.com/kwonhyucknae/algorithm_study/blob/master/src/com/leetCode/problem/Generate%20Parentheses.java