find_sign.py

def coerce_join(iterable):                                          
    return ''.join(str(c) for c in iterable)                        
                                                                    
                                                                    
def find_signs(rhs, total, lhs=None):                               
    if not rhs:                                                     
        # we could have a solution.                                 
        joined = coerce_join(lhs)                                   
        if eval(joined) == total:                                   
            yield joined                                            
    else:                                                           
        if lhs is None:                                             
            lhs = []                                                
            # No need for '+' before first digit.                   
            operators = ('-', '')                                   
        else:                                                       
            operators = ('+', '-', '')                              
                                                                    
        for operator in operators:                                  
            # make a copy of our branches per operator.             
            branch_rhs = rhs[:]                                     
            branch_lhs = lhs[:]                                     
            next_ = branch_rhs.pop(0)                               
            branch_lhs.append(operator)                             
            branch_lhs.append(next_)                                
            for result in find_signs(branch_rhs, total, branch_lhs):
                yield result                                   



# >>> list(answers.find_signs(range(1, 10), 100))                                                
# ['-1+2-3+4+5+6+78+9', '1+2+3-4+5+6+78+9', '1+2+34-5+67-8+9', '1+23-4+5+6+78-9', '1+23-4+56+7+8+9', '12
# +3+4+5-6-7+89', '12+3-4+5+67+8+9', '12-3-4+5-6+7+89', '123+4-5+67-89', '123+45-67+8-9', '123-4-5-6-7+8
# -9', '123-45-67+89']                                                                                  
# >>> len(_)                                                                                            
# 12