Generate balanced parentheses using Heap's Algorithm

BalancedParanthesesGenerator.swift

import Foundation

final class Solution {
    // Using a Set for result storage prevents unintended duplicates from being added.
    private var result: Set<[Character]> = Set()

    func generateParans(_ num: Int) {
        // Build the seed array for sending into Heap's Algorithm gen function.
        // We create an array of `num` opening parans and combine it with an
        // array of `num` closing parans.
        let beg: [Character] = Array(repeating: "(", count: num)
        let end: [Character] = Array(repeating: ")", count: num)
        var seed = beg + end
        guard seed.count == num * 2 else {
            fatalError("Seed generation failed!")
        }
        heapsAlgorithm(&seed, seed.count)
    }

    func checkResult(_ num: Int) {
        var count: Int = 0
        var valid: [String] = []
        result.forEach { charArr in
            let g = String(charArr)
            if isBalanced(input: g) {
                count += 1
                valid.append(g)
            }
        }
        print("""
        Generating all valid permutations of (\(num)) parantheses results in (\(count)) balanced permutations. 
        They are:
        \(valid)
        """)
    }

    private func heapsAlgorithm(_ a: inout [Character], _ n: Int) {
        if n == 1 {
            result.insert(a) // Completed our swaps, add to the result Set
            return
        }

        // This algorithm operates by locking the final position of the array in place
        // while recursively calling itself to swap the rest of the elements to the
        // left. Once they are swapped between all their positions the final element
        // is swapped and it starts over again until all permutations are created.
        for i in 0..<(n - 1) {
            heapsAlgorithm(&a, n - 1)
            if n % 2 == 0 { // If we are on an even index, swap the current element with the one to the left
                a.swapAt(n - 1, i)
            } else { // Otherwise swap the current element with the head
                a.swapAt(n - 1, 0)
            }
        }
        heapsAlgorithm(&a, n - 1)
    }

    private func isBalanced(input: String) -> Bool {
        var stack: [Character] = []
        for char in input {
            if char == "(" {
                // Opening parans can always be added to the stack directly.
                stack.append(char)
            }
            else if char == ")" {
                // When we encounter a closing parans we need to pop the top
                // of the stack and check that it is a closing parans. If it
                // isn't, then we have failed the balanced check.
                let c = stack.popLast()
                guard c == "(" else { return false }
            }
            else { return false } // Edge case check for if invalid characters are passed in.
        }
        // After going through the stack if anything is left over then
        // we automatically fail the balanced check.
        if !stack.isEmpty { return false }
        return true
    }
}