How to check if a given string is sum-string in Python

In this tutorial, we will see what is a sum-string and then a short code to check if the given string is a sum-string in Python. The rule to check if a string is sum string is pretty simple. We will use the backtracking technique for this purpose. Without any further delay, let’s get started.

Example of sum string:

String = “1235”
“1” +  “2” = 3
“2” + “3” = 5
This is a sum string

String = “1235813”
“1” + “2” = “3”
“2” + “3” = “5”
“5” + “8” = “13”
This is a sum string

String = “112223”
“1”+”1” = “2”
“2” + “2” = “4”
This is not a sum string

The rule for checking if a string is a sum-string is –

Substring(i,x) + substring(x+1,j) = substring(j+1,y)
and
Substring(x+1,j) + substring(j+1,y) = substring(y+1,k) 
and so on till the end

Now, to check if a string is a sum-string, we will create a class SumString and use the backtracking technique as mentioned earlier. We will start at index 0 of the string and go on to check further. Let’s see the code.

Check if a given String is Sum-string in Python

class SumString(object):
    
    def isSumString(self,string):
        
        def check(s,ind,ans):
            # first if
            # if the whole string is checked
            if ind == len(s) and len(ans) >2:
                return True
            
            res = False
            for i in range(ind,len(s)):
                # extract substrings
                temp = s[ind:i+1]
                # second if
                # check if the sum of two previous subtrings is not equal to current 
                #substring
                if len(ans) >=2 and int(ans[-2]) + int(ans[-1]) != int(temp):
                    continue
                ans.append(temp)
                res = res or check(s,i+1,ans)
                ans.pop()
                
            return res
        
        return check(string,0,[])

Let’s understand this code using the simplest example of “123”. First, we instantiate the SumString class. Then we call the isSumString constructor which calls the check function. In the very first call, check(s,ind,ans) , len(s) = 3, ind = 0 and ans = [ ]. Both the “if” conditions are false.

In the second call, the parameters for the function are check("123", 1, ["1"]). The for loop starts from i =1 . Both the “if” conditions are false and “ans” becomes ans = ["1","2"].

In the third call, the parameters for the function are check("123", 2, ["1","2"]). The for loop starts from i = 2 . Both the “if” conditions are false and “ans” becomes
ans = ["1","2","3"].

In the fourth call, the parameter for the function are check("123", 3, ["1","2","3"]). Value of “ind” is 3 which is equal to “len(s)” so the first “if” condition becomes true and the function returns “True“. The program flow path is traced back and the initial first call which was made to the check function returns “True” to isSumString.

Likewise, you can take any string and check if it is a sum-string by following this procedure.

Some of the example outputs are printed here.

lets_check = SumString()

print("1.", lets_check.isSumString("112223"))    

print("2.", lets_check.isSumString("2567"))

print("3.", lets_check.isSumString("1235"))

print("4.", lets_check.isSumString("1235813"))

print("5.", lets_check.isSumString("15643"))

print("6.", lets_check.isSumString("0000"))

print("7.", lets_check.isSumString("111111111"))

Output:

1. False
2. False
3. True
4. True
5. False
6. True
7. False