Split a given number so that their sum adds to another given number

Question

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

Answer 1

Python 2

Python 2 is end-of-life, and Python 3 has a lot of advantages now:

• f-strings
• unicode support
• ...

More info here, here and on many other places.

If you need python 2.7, try to make your code compatible with both.

Split it into functions

You do that to a limited extent with break_down, but you can do it in a lot more places:

• parsing the input
• breaking the input into parts
• calculating the sum of the parts

• output

  from __future__ import print_function
  

Parsing the input

you do input("") a lot. If you skip the "", you can test your input parsing with something like

input_str = '''4
15112 28
120012 33
123 123
15489001 10549'''
input = iter(input_str.split('\n')).__next__

In the parsing of the input, you iterate over the string, insert a space between characters and then split on the space, while all you need to do is list(text).

So I would go for:

def parse_input():
    cases = int(input())
    for _ in range(cases):
        question, answer = input().split()
        yield question, answer

list(parse_input())

[('15112', '28'), ('120012', '33'), ('123', '123'), ('15489001', '10549')]

Splitting the input

This is what your break_down does. But you format its answer as a str with spaces between the numbers. Why not just yield the ints immediately with int(''.join(words[i:j])) instead of ' '.join(words[i:j])

instead of words for the collection of digits, I would use digits as name. Same with ns and n, I don't find their purpose clear by their name, but I can't find a good, clear name instantly either.

For python 2 and 3 portability, you will need to do list(range(...)), because you iterate over ns twice

And your solution with zip((0,) + idxs, idxs + (None,)) is also well found, but not clear what exactly it does. The same idea can be made more clear using the pairwise itertools recipe.

def pairwise(iterable):
    '''
    s -> (s0,s1), (s1,s2), (s2, s3), ...
    https://docs.python.org/3/library/itertools.html#itertools-recipes
    '''
    a, b = itertools.tee(iterable)
    next(b, None)
    return zip(a, b)

def break_down(text):
    digits = list(text)
    ns = list(range(1, len(digits))) # n = 1..(n-1)
    for n in ns: # split into 2, 3, 4, ..., n parts.
        for idxs in itertools.combinations(ns, n):
            idxs = (0, *idxs, None)
            yield tuple(int(''.join(digits[i:j])) for i, j in pairwise(idxs))

Calculating the sum

instead of

    x=[int(i) for i in x]


    for i in x:
        #calculating sum
        sum+=i

you can use the builtin sum (if you don't overwrite the name with a variable like here) total = sum(map(int, x) does the same as these original 3 lines.

But since we already got ints from the previous part instead of strings, just sum will do:

def check_sum(question, target):
    for parts in breakdown(question):
        if sum(parts) == target:
            yield parts

formatting the answer can also be more efficient and clear than manually putting '+' between all parts.

def format_answer(answer):
    return '+'.join(map(str, answer))

Putting it together

def solve_query(query):
    question, target = query
    target = int(target)
    answer = next(find_sums(question, target))
    return format_answer(answer)

and then, behind a main guard:

if __name__ == '__main__':
    queries = parse_input()
    for query in queries:
        print(solve_query(answer))