Swift implementation with docs and full comments

• This is a variation on some solutions in this forum but written in Swift. This problem has a large number of permutations which I attempt to capture in the comments.

``````class Solution {

// Recursion
// - Parameters:
//     - results: String array of valid math operation strings to return
//     - result: String with current operation string being constructed
//     - digits: Int array with the individual digits
//     - target: Int with the target operation final value
//     - offset: Current position in the digits array
//     - mr:     MR like a calculator holding the result of the last operation
//     - prior:  Special param to help multiplication which is backward looking due to order of operations (BOMDAS)
func dfs(_ results: inout [String], _ result: String, _ digits: [Int], _ target: Int, _ offset: Int, _ mr: Int, _ prior: Int) {

// if we're evaluated all the digits, we're at the end of the recrusion
if offset == digits.count {
// save the result string if the MR value equal to our target
if target == mr {
results.append(result)
}
return
}

// walk the down digit array from the current offset
for i in offset..<digits.count {
// zeros are handled slightly differently
// to account for 10, if we see a zero but we're not at the
// current offset, we need to treat it like a 10
if i != offset && digits[offset] == 0 {
break
}

// build the current number from the digits
var val = 0
// i+1 is not bounded, so make sure we
// don't exceed the digit array bounds
for x in offset..<i+1 where x < digits.count {
// increase the existing value of val by a power of 10 on each iteration
val *= 10
val += digits[x]
}

// if we're at the first digit, there's no operation possible
if offset == 0 {
// the first digit is simple, initialize the string and MR is digit
dfs(&results, result + String(val), digits, target, i + 1, val, val)
} else {
// addition: add the digit to the string and add it to MR, track it in case we mul next
dfs(&results, result + "+" + String(val), digits, target, i + 1, mr + val, val)
// substraction: add the digit to the string and minus it from MR, track it in case we mul next
dfs(&results, result + "-" + String(val), digits, target, i + 1, mr - val, -val)
// multiplication: add the digit to the string, but we have an order of operations to deal with
// BOMDAS, so minus the prior value and add the multiplied value to MR, track the multiplied value in prior
dfs(&results, result + "*" + String(val), digits, target, i + 1, mr - prior + (prior * val), prior * val)
}
}
}

// the problem description is a bit vague, but we don't just
// care about single digits, it's all possible numbers comprised
// of those digits, this greatly increases the number of permutations
// to O(n^2)
func addOperators(_ num: String, _ target: Int) -> [String] {
var results: [String] = []

// ensure we have evaluatble input
if num.count == 0 {
return results
}

// split the string into an array of digits
let digits = Array(num).map({Int(String(\$0))!})

// recurse from index zero
dfs(&results, "", digits, target, 0, 0, 0)

return results
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.