Return to Revisions

Task

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.

Input

• 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.

Output

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]

Example Input

4
15112 28
120012 33
123 123
15489001 10549

Example Output

15+11+2
1+20+012
123
1548+9001