#22. Generate Parentheses

모든 유효한 괄호를 만드는 문제로, 간단한 문제였다.

괄호문자열이 구성되는 매 상태마다 (보다 )가 많으면 안되는 것만 알면 쉽게 해결 가능하다.

항상 시작은 괄호를 열어야 되므로, 완전탐색으로 구현가능하다.

각 재귀호출마다

1. 모든 괄호를 소진했으면(열린괄호와 닫힌괄호의 갯수가 n의 갯수와 같으면) 답을 선택하고 종료.
2. 열 수 있는 괄호가 남아있으면 괄호를 열고 재귀호출
3. 현재까지 열린 괄호보다 닫힌 괄호가 적으면 괄호를 닫고 재귀호출

2번과 3번 두 경우를 조건판단해서 구현하면 된다.

var (
    N int
    buf []byte
    ans []string
)

func generateParenthesis(n int) []string {
    N = n
    ans = make([]string, 0, 16)
    buf = make([]byte, n*2)
    solve(0, 0, 0)

    return ans
}

// i는 괄호의 위치
// o는 열린(open) 괄호의 갯수
// c는 닫힌(close) 괄호의 갯수
func solve(i, o, c int) {
    if i == N*2 && o == N && c == N {
        ans = append(ans, string(buf))
        return
    }

    if o < N {
        buf[i] = '('
        solve(i+1, o+1, c)
    }

    if c < o {
        buf[i] = ')'
        solve(i+1, o, c+1)
    }
}