[LeetCode][Kotlin] 22. Generate Parentheses

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

n쌍의 괄호가 주어졌을 때, 올바르게 구성된 괄호의 모든 조합을 생성하는 함수를 작성하세요.

 

Example 1:

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

 

Example 2:

Input: n = 1

Output: ["()"]

 

Constraints:

• 1 <= n <= 8

---

코드 1

class Solution {
    fun generateParenthesis(n: Int): List<String> {
        val stack = mutableListOf<String>()
        val res = mutableListOf<String>()

        fun backtrack(openN: Int, closedN: Int) {
            if (openN == n && closedN == n) {
                res.add(stack.joinToString(""))
                return
            }

            if (openN < n) {
                stack.add("(")
                backtrack(openN + 1, closedN)
                stack.removeAt(stack.lastIndex)
            }

            if (closedN < openN) {
                stack.add(")")
                backtrack(openN, closedN + 1)
                stack.removeAt(stack.lastIndex)
            }
        }

        backtrack(0, 0)
        return res
    }
}

 

코드 2

class Solution {
    fun generateParenthesis(n: Int): List<String> {
        val answer = mutableListOf<String>()

        fun backtrack(openN: Int, closedN: Int, current: String) {
            if (openN == n && closedN == n) {
                answer.add(current)
                return
            }

            if (openN < n) {
                backtrack(openN + 1, closedN, current + "(")
            }

            if (closedN < openN) {
                backtrack(openN, closedN + 1, current + ")")
            }
        }

        backtrack(0, 0, "")
        return answer
    }
}