LeetCode: Expression Add Operators

Posted on March 13, 2018July 26, 2020 by braindenny

Expression Add Operators

Similar Problems:

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Examples:

"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## https://code.dennyzhang.com/expression-add-operators
// Basic Ideas: backtracking
//
//  No leading 0
//  Avoid overflow
//  How to deal with 2+3*2, 2+3*2*4
//
// Complexity: Time ?, Space ?
import "strconv"
func dfs(combination string, pos int, res *[]string, num string, target int64, val int64, lastNum int64) {
    if pos == len(num) && val == target {
        *res = append(*res, string(combination))
        return
    }
    for i:=pos; i<len(num); i++ {
        // Invalid leading 0
        if num[pos] == '0' && i!=pos {
            break
        }
        // Take num[pos:i] as a value to operate
        v, _ := strconv.Atoi(num[pos:i+1])
        cur := int64(v)
        if pos == 0 {
            dfs(num[pos:i+1], i+1, res, num, target, cur, cur)
        } else {
            // add +
            dfs(combination+"+"+num[pos:i+1], i+1, res, num, target, val+cur, cur)
            // add -
            dfs(combination+"-"+num[pos:i+1], i+1, res, num, target, val-cur, -cur)
            // add *
            dfs(combination+"*"+num[pos:i+1], i+1, res, num, target, (val-lastNum)+lastNum*cur, lastNum*cur)
        }
    }
}

func addOperators(num string, target int) []string {
    res := []string{}
    dfs("", 0, &res, num, int64(target), int64(0), int64(0))
    return res
}

Post Views: 4