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