// Solution A: Unwind the recursion using DFS

func printXY(_ n: Int) -> [String] {
    
    var explored = Set<Int>()
    var stack = [n]
    var output = [String]()
    
    while let last = stack.last {
        
        let next = last - 1
        
        if last == 1 {
            // base case
            output = ["X", "Y"]
            explored.insert(last)
            
        } else {
            
            if explored.contains(next) {
                
                var newOutput = [String]()
                for element in output {
                    newOutput.append(element + "X")
                    newOutput.append(element + "Y")
                }
                
                output = newOutput
                
            } else {
                explored.insert(next)
                stack.append(next)
                continue
            }
        }
        
        stack.popLast()
    }
    
    return output
}

let res = printXY(4)
res.forEach { print($0) }


// Solution B: no stack

let n = 4
var array = [Character](repeating: "X", count: n)

outerLoop: do {
    print(String(array))

    for i in 0..<n {
        if array[i] == "X" {
            array[i] = "Y"
            continue outerLoop
        }
        array[i] = "X"
    }
}


// Solution C: Recursive

func printXY(_ n: Int) -> [String] {
    guard n > 1 else {
        return ["X", "Y"]
    }

    let next = printXY(n - 1)

    var output = [String]()
    for element in next {
        output.append(element + "X")
        output.append(element + "Y")
    }

    return output
}

let res = printXY(4)
res.forEach { print($0) }