https://leetcode.com/problems/expression-add-operators/description/

expression-add-operators.py

def result(o):
    return eval(o)

def get_all_options(num, tail, target):
    if len(num) == 0:
        return {}
    if len(num) == 1:
        return {int(num): [ num ] }
    last_dict = get_all_options(num[:-1], num[-1] + tail, target)
    curr_dict = {}
    for r, os in last_dict.items():
        for o in os:
            po = o[:]
            po += '+' + num[-1]
            po_result = result(po)
            curr_dict[po_result] = curr_dict.get(po_result, list())
            curr_dict[po_result].append(po)            
            
            mo = o[:]
            mo += '-' + num[-1]
            mo_result = result(mo)
            curr_dict[mo_result] = curr_dict.get(mo_result, list())
            curr_dict[mo_result].append(mo)            
            
            mto = o[:]
            mto += '*' + num[-1]
            mto_result = result(mto)
            curr_dict[mto_result] = curr_dict.get(mto_result, list())
            curr_dict[mto_result].append(mto)            
            
            if len(o) >= 2 and (not o[-2].isdigit()) and o[-1] == '0':
                continue
                
            no = o + num[-1]
            no_result = result(no)
            curr_dict[no_result] = curr_dict.get(no_result, list())
            curr_dict[no_result].append(no)
#    for r in curr_dict.keys():
#        if len(tail) and r - int(tail) > target:
#            del curr_dict[r]
        
    return curr_dict

class Solution(object):
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        result = get_all_options(num, '', target);
        if target in result:
            return result[target]
        return []