Given a string of digits, the task is to check if it is a ‘sum-string’. A string S is called a sum-string if a rightmost substring can be written as a sum of two substrings before it and the same is recursively true for substrings before it. 
 
Example 1:
Input:
12243660
Output:
1
Explanation:
"12243660" is a sum string. As we 
can get, 24 + 36 = 60 & 12 + 24 = 36.
 
Example 2:
Input:
1111112223
Output:
1
Explanation:
"1111112223" is a sum string. As we 
can get, 111+112 = 223 & 1+111 = 112.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function isSumString() which takes the string S and returns 1 is S is a sum-string otherwise returns 0.
 
Expected Time Complexity: O(|S|^{2})
Expected Auxiliary Space: O(|S|)
 
Constraints:
1<=|S|<=10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Complete search

Starter code: #User function Template for python3

class Solution:

    def isSumString (ob,S):

        # code here 

Solutions:
class Solution:

	def isSumString(self, S):
		n = len(S)
		for l in range(1, n):
			sub_arr = int(S[n - l:])
			if self.is_sum_string_sub(S, n - l, sub_arr, None) == 1:
				return 1
		return 0

	def is_sum_string_sub(self, S, limit, sub_arr, sub_1):
		sub_2 = 0
		if sub_1 is None:
			sub_1 = 0
			for l_1 in range(1, limit + 1):
				sub_1 = int(S[limit - l_1:limit])
				if sub_1 > sub_arr:
					return 0
				for l_2 in range(1, limit - l_1 + 1):
					sub_2 = int(S[limit - l_1 - l_2:limit - l_1])
					if sub_1 + sub_2 > sub_arr:
						break
					if sub_1 + sub_2 == sub_arr:
						if limit - l_1 - l_2 == 0:
							return 1
						if self.is_sum_string_sub(S, limit - l_1 - l_2, sub_1, sub_2) == 1:
							return 1
		else:
			for l_2 in range(1, limit + 1):
				sub_2 = int(S[limit - l_2:limit])
				if sub_1 + sub_2 > sub_arr:
					break
				if sub_1 + sub_2 == sub_arr:
					if limit - l_2 == 0:
						return 1
					if self.is_sum_string_sub(S, limit - l_2, sub_1, sub_2) == 1:
						return 1
		return 0


class Solution:

	def isSumString(ob, S):

		def rec(s, beg, l1, l2):
			s1 = s[beg:beg + l1]
			s2 = s[beg + l1:beg + l1 + l2]
			s3 = str(int(s1) + int(s2))
			l3 = len(s3)
			if beg + l1 + l2 + l3 > len(s):
				return False
			elif s3 == s[beg + l1 + l2:beg + l1 + l2 + l3]:
				if beg + l1 + l2 + l3 == len(s):
					return True
				return rec(s, beg + l1, l2, l3)
			return False
		S = str(S)
		for i in range(1, len(S)):
			for j in range(1, len(S) - i):
				if rec(S, 0, i, j):
					return 1
		return 0


class Solution:

	def isSumString(self, s: str) -> int:
		n = len(s)
		for i in range(1, n):
			for j in range(i + 1, n):
				x = int(s[:i])
				y = int(s[i:j])
				k = j
				while k < n:
					z = x + y
					sz = str(z)
					if sz != s[k:k + len(sz)]:
						break
					x = y
					y = z
					k = k + len(sz)
				if k == n:
					return 1
		return 0


class Solution:

	def solve(self, i, S, P, lst=[]):
		if i >= len(S) and P > 2:
			return True
		if i >= len(S) and P <= 2:
			return False
		for j in range(i, len(S)):
			if P < 2:
				lst.append(S[i:j + 1])
				if self.solve(j + 1, S, P + 1, lst):
					return True
				lst.pop()
			else:
				ele = S[i:j + 1]
				if int(lst[-1]) + int(lst[-2]) == int(ele):
					lst.append(ele)
					if self.solve(j + 1, S, P + 1, lst):
						return True
					lst.pop()
		return False

	def isSumString(self, S):
		if self.solve(0, S, 0):
			return 1
		return 0


class Solution:

	def isSumString(ob, S):

		def dfs(S, s1, s2, s3, i):
			if i == len(S):
				if s3 != '' and int(s1) + int(s2) != int(s3):
					return False
				return True
			if int(s3 + S[i]) > int(s1) + int(s2):
				return False
			if int(s3 + S[i]) == int(s2) + int(s1):
				return dfs(S, s2, s3 + S[i], '', i + 1)
			if int(s3 + S[i]) < int(s2) + int(s1):
				return dfs(S, s1, s2, s3 + S[i], i + 1)
		y = False
		s1 = ''
		for i in range(len(S)):
			s1 = s1 + S[i]
			s2 = ''
			for j in range(i + 1, len(S) - 1):
				s2 = s2 + S[j]
				y = y or dfs(S, s1, s2, '', j + 1)
		if y:
			return 1
		return 0


class Solution:

	def isSumString(ob, S):

		def rec(f, s, res):
			if len(res) == 0:
				return True
			tot = str(f + s)
			l = len(tot)
			if tot == res[:l]:
				return rec(s, int(tot), res[l:])
		for i in range(1, len(S) - 1):
			for j in range(i + 1, len(S)):
				f = S[:i]
				s = S[i:j]
				if rec(int(f), int(s), S[j:]):
					return 1
		return 0


class Solution:

	def isSumString(ob, S):

		def getsum(s1, s2):
			if s1 == '' and s2 == '':
				return ''
			if s1 == '':
				return s2
			if s2 == '':
				return s1
			first = int(s1)
			second = int(s2)
			return str(first + second)

		def check(s, beg, l1, l2):
			s1 = s[beg:beg + l1]
			s2 = s[beg + l1:beg + l1 + l2]
			s3 = getsum(s1, s2)
			if len(s3) > len(s) - l1 - l2 - beg:
				return False
			if s3 == s[beg + l1 + l2:beg + l1 + l2 + len(s3)]:
				if beg + l1 + l2 + len(s3) == len(s):
					return True
				return check(s, beg + l1, l2, len(s3))
			return False
		n = len(S)
		for i in range(1, n):
			for j in range(1, n - i):
				if check(S, 0, i, j):
					return 1
		return 0


class Solution:

	def first(ob, S):
		possib = []
		for i in range(1, len(S) - 2):
			s1 = S[0:i]
			for j in range(i + 1, len(S) - 1):
				s2 = S[i:j]
				s3 = str(int(s1) + int(s2))
				if s3 == S[j:j + len(s3)]:
					possib.append([s2, s3, j + len(s3)])
		return possib

	def isSum(ob, S, s1, s2, k):
		if k == len(S):
			return True
		s3 = str(int(s1) + int(s2))
		if s3 == S[k:k + len(s3)]:
			return ob.isSum(S, s2, s3, k + len(s3))
		else:
			return False

	def isSumString(ob, S):
		possib = ob.first(S)
		for i in possib:
			if ob.isSum(S, i[0], i[1], i[2]):
				return 1
		return 0


class Solution:

	def isSumString(ob, S):

		def rec(first, second, rest):
			if len(rest) == 0:
				return True
			total = str(first + second)
			l = len(total)
			if total == rest[:l]:
				return rec(second, int(total), rest[l:])
		for i in range(1, len(S) - 1):
			for j in range(i + 1, len(S)):
				first = S[:i]
				second = S[i:j]
				if rec(int(first), int(second), S[j:]):
					return 1
		return 0


class Solution:

	def getSequenceLength(self, x0, x1, pos, S):
		if pos == len(S):
			return 0
		x2 = str(x0 + x1)
		if pos + len(x2) > len(S):
			return -1
		if S[pos:pos + len(x2)] != x2:
			return -1
		else:
			seq_len = self.getSequenceLength(x1, x0 + x1, pos + len(x2), S)
			if seq_len == -1:
				return -1
			return 1 + seq_len

	def isSumString(self, S):
		for i in range(1, len(S) - 1):
			for j in range(i + 1, len(S)):
				x0 = int(S[:i])
				x1 = int(S[i:j])
				seq_len = self.getSequenceLength(x0, x1, j, S)
				if seq_len == -1:
					continue
				return 1
		return 0


class Solution:

	def __init__(self):
		self.flag = False
		self.ans = False

	def checkSum(self, prev, num, numprev, lenn, n):
		while prev < lenn:
			wenge = str(num + numprev)
			t = len(wenge)
			if prev + t > lenn:
				return ('Length over', False)
			if n[prev:prev + t] == wenge:
				numprev = num
				num = int(n[prev:prev + t])
				prev = prev + t
			else:
				return ('Condition Fail', False)
		return (num, True)

	def isSumString(self, S):
		mini = len(S)
		if mini < 3:
			return False
		for i in range(1, mini):
			if self.flag:
				break
			for j in range(i + 1, mini):
				temp = int(S[:i]) + int(S[i:j])
				k = len(str(temp))
				if self.flag:
					break
				if S[j:j + k] == str(temp):
					(self.ans, self.flag) = self.checkSum(j + k, temp, int(S[i:j]), mini, S)
		return int(self.flag)


class Solution:

	def isSumString(ob, s):
		len_s = len(s)

		def rec(s1, s2, en2):
			s3 = str(s1 + s2)
			len_s3 = len(s3)
			if len_s3 > len_s - en2 - 1:
				return 0
			elif len_s3 == len_s - en2 - 1 and s[en2 + 1:] == s3:
				return 1
			else:
				return rec(s2, int(s3), en2 + len_s3)
		for i in range(1, len_s - 1):
			s1 = int(s[0:i])
			for j in range(i + 1, len_s):
				s2 = int(s[i:j])
				if rec(s1, s2, j - 1):
					return 1
		return 0


class Solution:

	def isSumString(ob, S, idx=0, val1=None, val2=None, cnt=0):
		if idx == len(S):
			return 1 if cnt > 2 else 0
		if val1 == None:
			tmp = ''
			for i in range(idx, len(S) // 3 + 1):
				tmp += S[i]
				if ob.isSumString(S, i + 1, tmp, val2, cnt + 1):
					return 1
			return 0
		elif val2 == None:
			tmp = ''
			for i in range(idx, len(S) - 1):
				tmp += S[i]
				if ob.isSumString(S, i + 1, val1, tmp, cnt + 1):
					return 1
			return 0
		else:
			req = str(int(val1) + int(val2))
			if idx + len(req) <= len(S):
				new = S[idx:idx + len(req)]
				if new == req and ob.isSumString(S, idx + len(req), val2, new, cnt + 1):
					return 1
			return 0


class Solution:

	def solve(ob, s, idx, a, b, found):
		if idx == len(s):
			if found == True:
				return 1
			return 0
		t = ''
		for i in range(idx, len(s)):
			t += s[i]
			if a == -1:
				if ob.solve(s, i + 1, int(t), b, found):
					return 1
			elif b == -1:
				if ob.solve(s, i + 1, a, int(t), found):
					return 1
			elif a + b == int(t):
				if ob.solve(s, i + 1, b, int(t), True):
					return 1
		return 0

	def isSumString(ob, S):
		return ob.solve(S, 0, -1, -1, 0)