You are given a string S containing only decimal digits ('0' through '9') and a number N. Your task is to insert an arbitrary number (including zero) of plus signs '+' into S in order to form a valid expression whose value is equal to N.
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains a string S, followed by a space and an integer N.
For each test case, print a single line containing one string — your solution, i.e. the expression obtained after inserting some plus signs into S. If there are multiple solutions, you may output any one. It is guaranteed that at least one solution exists.
My code is not very optimized but gives the correct answer. Help me find an optimized version.
import itertools case=input("") for i in range(case): text,text2=str(raw_input("")).split() text=list(text) text1="" l= def break_down(text): words = text.split() ns = range(1, len(words)) # n = 1..(n-1) for n in ns: # split into 2, 3, 4, ..., n parts. for idxs in itertools.combinations(ns, n): yield [' '.join(words[i:j]) for i, j in zip((0,) + idxs, idxs + (None,))] for i in text: #to add whitespace in between so that split() functions separates it correctly text1=text1+i text1=text1+" " for x in break_down(text1): #this part calls the generator and sums every iteration sum=0 answer="" for i in range(len(x)): #removing the whitespaces that were added before x[i]=x[i].replace(" ","") #converts string to int so that it actually adds number not concatenates them x=[int(i) for i in x] for i in x: #calculating sum sum+=i if sum==int(text2): l=x #if the sum is equal to given number then it prints it out in the asked manner for i in l: i=str(i) answer+=i answer+="+" if int(text1.replace(" ",""))==int(text2): print int(text1.replace(" ","")) else: print answer[:len(answer)-1]
4 15112 28 120012 33 123 123 15489001 10549
15+11+2 1+20+012 123 1548+9001