#Given numbers from 1 to 9
#generate string such that either addition or subctraction of the numbers should fetch you
# the total of 100
#example 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100
class Approch1(object):
    def __init__(self):
        self.digits = [1,2,3,4,5,6,7,8,9]

    def logic2(self, index, output, s):
        if(index == len(self.digits)):
            if(s==100):
                print output, s
            return
        #add
        output.append(self.digits[index])
        self.logic2(index+1, output, s+self.digits[index])
        output.pop()
        #subctract
        output.append(-self.digits[index])
        self.logic2(index+1, output, s-self.digits[index])
        output.pop()
        #multiply
        if(output):
            top = output.pop()
            #*********************************************
            #this is where I went wrong in previous approches  #*
            n = 0                                                                       #*
            if(top > 0):                                                              #*
                n = (top*10)+self.digits[index]                            #*
            else:                                                                      #*
                n = (top*10)-self.digits[index]                           #*
            #*********************************************
            output.append(n)                                                
            self.logic2(index+1, output, (s-top)+n)
            #output.pop() <- add this line back and see how it changes in memory, and thats why I went wrong previously too. because I put this in for loop
            #lesson learnt, dont use for loop when you have less instances and when its not actually required.    
                    
    def solution(self):
        self.logic2(0, [], 0)

#Main
o = Approch1()
o.solution()