LeetCode: Generate Parentheses

백트랙킹 + 스택괄호를 조합한 문제였다. 두 가지 메서드를 만들어서 처리했다.

1. n개의 모든 괄호 조합을 만드는 pick(toPick:)
2. 문자열 배열이 올바른 괄호 조합인지 판별하는 isWell(_:)

중복이 있을까봐 Set으로 저장해서, 정렬해서 반환하는 걸로 해결.

 

문제

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

 

내가 작성한 코드

Swift

class Solution {
    func generateParenthesis(_ n: Int) -> [String] {
        let bracket = ["(", ")"]
        var result = [[String]]()
        var picked = [String]()
        func pick(toPick: Int) {
            if toPick == 0 {
                result.append(picked)
                return
            }

            for i in 0..<2 {
                picked.append(bracket[i])
                pick(toPick: toPick - 1)
                picked.removeLast()
            }
        }

        func isWell(_ arr: [String]) -> Bool {
            var count = 0
            for char in arr {
                if char == "(" {
                    count += 1
                } else {
                    count -= 1
                    if count < 0 {
                        return false
                    }
                }
            }

            return count == 0 ? true : false
        }

        pick(toPick: n * 2)

        var answer = Set<String>()

        for r in result {
            if isWell(r) {
                answer.insert(r.joined())
            }
        }

        return answer.sorted()
    }
}