How to find all the sub strings that add up to a certain sum in python?

Question

Suppose I have a number 3523014 as a string. How can i find all the set of sub strings combined in form of a list, that add up to a certain digit say 10. I have written a code but i gives me a output of only few sub strings which are searched linearly.

Please fix the code -

def find_ten_substring(num_str):
        str1=""
        list1=[]
        a=0
        for i in range(0,len(num_str)):
                a=a+int(num_str[i])
                str1+=str(num_str[i])
                if(a==10):
                        a=0
                        list1.append(str1)
                        str1=""
        return(list1)


num_str="3523014"
print("The number is:",num_str)
result_list=find_ten_substring(num_str)
print(result_list)

The result comes as ['352']. The expected output should be ['5230', '23014', '523', '352']

Solution 1

This will solve your problem ....

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 


if __name__ == "__main__":
    num_str="3523014"
    print("The number is:",num_str)
    result_list=subset_sum(list(map(int,num_str)),10)
    print(result_list)

Solution 2

Let me start with what's wrong with your code..

• In For loop, after completing "3","5","2" as iterations, you have set your a as zero and str as empty, however, the next iteration for "For" loop is "3" at index-3 instead of it being "5" at index-1.
• from index-3, if you add all the values viz., 3,0,1,4, one still does not get sum as 10. Hence, you have only "352" as substring. To fix this, you can use two for loops.
  

Now my solution..

def find_ten_substring(num_str):
    ten_substr=[]         #list to store all substring
    for i in range(len(num_str)):
        sum=0
        sub_str=""
        for j in range(i,len(num_str)):
            sum+=int(num_str[j])
            if sum<10:
                sub_str+=num_str[j]
            elif sum==10:
                sub_str+=num_str[j]
                ten_substr.append(sub_str)
#checks if my current index is not my last index as at avoid index out of bound
#error in next line
                if (j!=len(num_str)-1):  
#checks if value at next index is "0". If true, it does not make sum as zero and
#substring as empty, instead continues with same value in next iteration.         
                    if (num_str[j+1]=="0"):
                        continue;
                    else:
                        break;
    return ten_substr; 

num_str="28353002"
print("The number is:",num_str)
result_list=find_ten_substring(num_str)
print(result_list)