GenerateStrings.swift

enum Parenthesis: String {
    case open = "("
    case closed = ")"
}

indirect enum Tree {
    case character(value: Parenthesis, next: Tree?) 
    
    var description: String {
        switch self {
        case let .character(value: parenthesis, next: tree):
            return "\(parenthesis.rawValue)\(tree?.description ?? "")"
        }
    }
    
    var count: Int {
        switch self {
        case let .character(value: Parenthesis, next: tree):
            return 1 + (tree?.count ?? 0)
        }
    }
    
    var string: String {
        switch self {
        case let .character(value: parenthesis, next: tree):
            return parenthesis.rawValue + (tree?.string ?? "")
        }
    }
    
    var isBalanced: Bool {
        var stack: [String] = []
        var iterator = self.string.makeIterator()
        while let next = iterator.next() {
            if next == "(" {
                stack.append("(")
            } else {
                if stack.isEmpty {
                    return false
                } else {
                    stack.popLast()    
                }
            }
        }
        return stack.isEmpty
    }
}


func generate(size n: Int) -> [Tree] {
    if n == 1 {
        return [
            Tree.character(value: .open, next: nil),
            Tree.character(value: .closed, next: nil)
        ]
    } else {
        let trees = generate(size: n - 1)
        let openTree = trees.map { Tree.character(value: .open, next: $0) }
        let closedTree = trees.map { Tree.character(value: .closed, next: $0) }
        return openTree + closedTree
    }
}

func generateStrings(size n: Int) -> [String] {
    generate(size: n)
        .filter { $0.isBalanced }
        .map { $0.string }
}

print(generateStrings(size: 12))

lacks backtracking