Expression Add Operators

Problem: Expression Add Operators

There is no tricks in solving this problem. All we can do is observe whether each possible operators-adding is equal to target or not. We can construct possible options into trees and do depth-first tree by recursive function so that we won't miss anything.

What's important about recursion? Details, detail, details! Details like recursion boundary and situation division matter.

Code in Python:

class Solution(object):

    def pushNumber(self, target, num, pos, product):
        res = []

        for i in xrange(pos, len(num)):

            if i == len(num) - 1:
                if product*int(num[pos:i+1]) == target:
                    res.extend([num[pos:i+1]])
                break

            addExpres = self.pushNumber(target-product*int(num[pos:i+1]), num, i+1, 1)
            res.extend([num[pos:i+1] + "+" + s for s in addExpres])

            subExpres = self.pushNumber(target-product*int(num[pos:i+1]), num, i+1, -1)
            res.extend([num[pos:i+1] + "-" + s for s in subExpres])

           mulExpres = self.pushNumber(target, num, i+1, product*int(num[pos:i+1]))
            res.extend([num[pos:i+1] + '*' + s for s in mulExpres])

            if num[pos] == "0":
                break

       return res

    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        return self.pushNumber(target, num, 0, 1)

It's apparent that we use iteration in function to deal with number concatenation and a product value to handle multiplication and minus. The general idea is to consider the basic operator as "+", all we need to decide is whether plus a single number, a concatenated number or a positive/negative product.

There may be questions on why not consider "-" as a basic operator as well. Since a-x=target, it's clear that x=a-target. Thus our code on "subExpres" will be like this:

subExpres = self.pushNumber(product*int(num[pos:i+1])-target, num, i+1, -1)

You can try it with number "123456789" and target 45. For possible answer "1+2+3+4+5-6times7-8times9" (actually not equals to 45), there will be 5-35 thus lead to wrong solution. Because if 1+2+3+4+5-x=45, then x=1+2+3+4+5-45, this conflicts with how we calculate addition. So we make minus as adding a negative number.