[ LeetCode ] 22 Generate Parentheses

📌 Problem

소괄호 ()가 n개의 쌍을 이룰 수 있는 모든 경우를 구하면 된다. 예를 들어 n = 1이면 ()만 가능하고 n = 2이면 ()(), (())이 가능하다. n은 1이상 8이하이다.

📌 Solution

백트래킹 방식으로 해결할 수 있다. 백트래킹을 할 때는 쌍이 이루어짐을 확인할 수 있는 stack과 왼쪽 오른쪽 소괄호 사용 가능 개수 그리고 현재까지의 사용 기록을 넘기면 된다.

모든 소괄호를 사용하였으면 현재까지의 기록을 결과에 추가하면 된다.

"("를 사용할 수 있는 경우는 "("의 남은 개수가 ")"가 남은 개수 이하이면서 0이 아닐 때이다.

")"를 사요할 수 있는 경우는 "("의 남은 개수가 ")"가 남은 개수 미만이면서 stack의 top이 "("일 때다.

📌 Code

import java.util.*

class Solution(
    private val list: MutableList<String> = mutableListOf()
) {
    fun generateParenthesis(n: Int): List<String> = list.apply {
        add(Stack(), n, n, "")
    }

    private fun add(stack: Stack<String>, left: Int, right: Int, history: String) {
        if (left + right == 0) list.add(history)
        else {
            if (left <= right && left != 0) {
                stack.push("(")
                add(stack, left - 1, right, "$history(")
                stack.pop()
            }
            if (left < right && stack.peek() == "(") {
                stack.pop()
                add(stack, left, right - 1, "$history)")
                stack.push("(")
            }
        }
    }
}