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}

见题面

见题面