# LeetCode Solution, Easy, 282. Expression Add Operators # [282. Expression Add Operators](https://leetcode.com/problems/expression-add-operators/) ### 題目敘述 Given a string `num` that contains only digits and an integer `target`, return _all possibilities to add the binary operators `'+'`, `'-'`, or `'*'`between the digits of `num` so that the resultant expression evaluates to the `target` value_. **Example 1:** Input: num = "123", target = 6 Output: ["1*2*3","1+2+3"] **Example 2:** Input: num = "232", target = 8 Output: ["2*3+2","2+3*2"] **Example 3:** Input: num = "105", target = 5 Output: ["1*0+5","10-5"] **Example 4:** Input: num = "00", target = 0 Output: ["0*0","0+0","0-0"] **Example 5:** Input: num = "3456237490", target = 9191 Output: [] **Constraints:** - `1 <= num.length <= 10` - `num` consists of only digits. - `-2^31 <= target <= 2^31 - 1` **Hint 1:** Note that a number can contain multiple digits. **Hint 2:** Since the question asks us to find **all** of the valid expressions, we need a way to iterate over all of them. (**Hint**: Recursion!) **Hint 3:** We can keep track of the expression string and evaluate it at the very end. But that would take a lot of time. Can we keep track of the expression's value as well so as to avoid the evaluation at the very end of recursion? **Hint 4:** Think carefully about the multiply operator. It has a higher precedence than the addition and subtraction operators. 1 + 2 = 3 1 + 2 - 4 --> 3 - 4 --> -1 1 + 2 - 4 * 12 --> -1 * 12 --> -12 (WRONG!) 1 + 2 - 4 * 12 --> -1 - (-4) + (-4 * 12) --> 3 + (-48) --> -45 (CORRECT!) **Hint 5:** We simply need to keep track of the last operand in our expression and reverse it's effect on the expression's value while considering the multiply operator. #### 題目翻譯 題目會給兩個參數，一個是字串 `num`，這個字串中都只包含數字。另一個參數是 `target`。然後想要找出在字串 `num` 中所有數字之間，可以插入 `+`, `-` 或 `*` 的 operator。最後可以等於 `target` 的所有組合。 ### 解法解析 這題的解法主要就是會使用到遞迴的方式，一層一層的去找出各種可能的答案。先以 python 的範例來說。在每次的遞迴時，先去判斷 index 是不是到最後了，如果是再來判斷總合是否與 `target` 相等，並且沒有剩下要執行的 operator，就會是要回傳的組合，儲存在 `answers` 裡面。在每次的遞迴裡面去分別計算如果插入 operator `-`, `+` 或 `*` 的各種情境。 #### 程式範例 ##### Python ```python class Solution: def addOperators(self, num: str, target: int) -> List[str]: N = len(num) answers = [] def recurse(index, prev_operand, current_operand, value, string): # Done processing all the digits in num if index == N: # If the final value == target expected AND # no operand is left unprocessed if value == target and current_operand == 0: answers.append("".join(string[1:])) return # Extending the current operand by one digit current_operand = current_operand*10 + int(num[index]) str_op = str(current_operand) # To avoid cases where we have 1 + 05 or 1 * 05 since 05 won't be a # valid operand. Hence this check if current_operand > 0: # NO OP recursion recurse(index + 1, prev_operand, current_operand, value, string) # ADDITION recurse(index + 1, current_operand, 0, value + current_operand, string + ['+', str_op]) # Can subtract or multiply only if there are some previous operands if string: # SUBTRACTION recurse(index + 1, -current_operand, 0, value - current_operand, string + ['-', str_op]) # MULTIPLICATION recurse(index + 1, current_operand * prev_operand, 0, value - prev_operand + (current_operand * prev_operand), string + ['*', str_op]) recurse(0, 0, 0, 0, []) return answers ``` ##### JavaScript ```javascript /** * @param {string} num * @param {number} target * @return {string[]} */ var addOperators = function (num, target) { const result = []; const backtrack = function (index, previous, current, path) { if (index === num.length && current === target) { result.push(path); return; } for (let i = index; i < num.length; i++) { if (i !== index && num[index] === '0') break; const cur = parseInt(num.substring(index, i + 1)); if (index === 0) { backtrack(i + 1, cur, cur, `${path}${cur}`); } else { backtrack(i + 1, cur, current + cur, `${path}+${cur}`); backtrack(i + 1, -cur, current - cur, `${path}-${cur}`); backtrack( i + 1, previous * cur, current - previous + previous * cur, `${path}*${cur}` ); } } }; backtrack(0, 0, 0, ''); return result; }; ``` ##### Go ```go func addOperators(num string, target int) []string { var ret = []string{} var buf = make([]byte, len(num)*2) // shared bytes buffer search(num, target, &ret, 0, 0, buf, 0) return ret } // `l` is the length of valid content in `buf` func search(num string, target int, ret *[]string, sum, diff int, buf []byte, l int) { if len(num) == 0 { if sum == target { *ret = append(*ret, string(buf[0:l])) } return } var n = 0 // try all valid digit combinations for i := 0; i < len(num); i++ { n = n*10 + int(num[i]-'0') var digits = num[0 : i+1] if l == 0 { copy(buf[l:], digits) search(num[i+1:], target, ret, sum+n, n, buf, l+i+1) } else { copy(buf[l+1:], digits) // one copy for the three operators buf[l] = '+' search(num[i+1:], target, ret, sum+n, n, buf, l+1+i+1) // add `1 operator + (i+1) digits` to the length of buffer buf[l] = '-' search(num[i+1:], target, ret, sum-n, -n, buf, l+1+i+1) buf[l] = '*' search(num[i+1:], target, ret, sum-diff+diff*n, diff*n, buf, l+1+i+1) } if i == 0 && num[i] == '0' { // skip any number starts with 0 break } } } ``` ##### Swift ```swift class Solution { func addOperators(_ num: String, _ target: Int) -> [String] { var numArr = Array(num).map {Int(String($0))!} var result = [String]() helper(numArr, target, 0, 0, 0, "", &result) return result } func helper(_ num: [Int], _ target: Int, _ index: Int, _ eval: Int, _ prevNum: Int, _ path: String, _ result: inout [String]) { if target == eval && num.count == index { result.append(path) return } if index == num.count { return } for i in index..() var digits = "" var target: Long = 0 fun addOperators(num: String, target: Int): List { if (num.length == 0) emptyList() this.target = target.toLong() this.digits = num this.recurse(0, 0, 0, 0, mutableListOf()) return this.answer } fun recurse(index: Int, prev: Long, cur: Long, value: Long, ops: MutableList) { val nums = this.digits var prevOp = prev var curOp = cur // Done processing all the digits in num if (index == nums.length) { // If the final value == target expected AND // no operand is left unprocessed if (value == this.target && curOp == 0L) { val sb = StringBuilder() ops.subList(1, ops.size).forEach { v -> sb.append(v) } this.answer.add(sb.toString()) } return } // Extending the current operand by one digit curOp = curOp * 10 + Character.getNumericValue(nums[index]) var rep = curOp.toString() val length = nums.length // To avoid cases where we have 1 + 05 or 1 * 05 since 05 won't be a // valid operand. Hence this check if (curOp > 0) { // NO OP recursion recurse(index + 1, prevOp, curOp, value, ops) } // ADDITION ops.add("+") ops.add(rep) recurse(index + 1, curOp, 0, value + curOp, ops) ops.removeAt(ops.size - 1) ops.removeAt(ops.size - 1) if (ops.size > 0) { // SUBTRACTION ops.add("-") ops.add(rep) recurse(index + 1, -curOp, 0, value - curOp, ops) ops.removeAt(ops.size - 1) ops.removeAt(ops.size - 1) // MULTIPLICATION ops.add("*") ops.add(rep) recurse(index + 1, curOp * prevOp, 0, value - prevOp + (curOp * prevOp), ops) ops.removeAt(ops.size - 1) ops.removeAt(ops.size - 1) } } } ```