Q:

# Find out the sum-string

There is a string given to you. You have to find out whether the given string is a sum string or not. For a string "12345168213" if it goes like this, "123" + "45" = "168" "45" + "168" = "213" then it is a sum string otherwise not.

```    Input:
Test case T
T no. of strings we have to check.

E.g.
3
"12345168213"
"123581321"
"15643"

Output:
If the string is a sum-string then you have to print
"It is a sum string"
and, if it is not then you have to print
"It is not a sum string".
```

Example

```    T=3

Str= "12345168213"

"123" + "45" = "168"
"45" + "168" = "213"
It is a sum string

Str= "123581321"
"1" + "2" = "3"
"2" + "3" = "5"
"3" + "5" = "8"
"5" + "8" = "13"
"8" + "13" = "21"
It is a sum string

Str= "15643"
"1" + "5" = "6"
"5" + "6" = "11"
It is not a sum string```

To find out the actual length of the first two substrings is a problem of combination. We will solve the problem using the backtracking process. If we break the problem into sub-problems like,

1. Find out the length of the first sub-string.
2. Find out the length of the second sub-string.
4. Check if the summation is the same as the next substring.
5. If yes, we will continue the process otherwise the string is not a sum string.
```    str.substring(i,j) + str.substring(j+1,k) = str.substring(k+1,l)
str.substring(j+1,k) + str.substring(k+1,l) = str.substring(l+1,m)
```

Where, ijklm is the position index on the substring of the string.

For the string "12345168213"

To find out the length of the first substring we will look for the all possible combination of the sub-string of the string from the starting index.

"1" , "12" , "123" , "1234" , "12345" , "123451" etc.

To find out the length of the second substring we will look for all possible combinations of the sub-string of the string from the last index of the first substring.

Let the first index= "123" then the all possible combinations are "4""45""451""4516" etc.

After calculating the summation of the two sub-strings will also find out the length of the result and take the next sub-string who has a length equal to that length.

If the two substrings are "123" and "45" after calculating the summation the result "168" we will calculate its length which is equal to 3 and take the next sub-string e.g. "168"

Both the resultant and the sub-string are the same therefore we will add up "45" and "168" and check with "213".

C++ implementation:

``````#include <bits/stdc++.h>
using namespace std;

{
int len1 = str1.length();
int len2 = str2.length();
int i = 1;
int carry = 0;
string str = "";

while ((len1 - i) >= 0 && (len2 - i) >= 0) {
int result = (str1[len1 - i] - '0') + (str2[len2 - i] - '0') + carry;
char ch = (result % 10) + '0';
str = ch + str;
carry = result / 10;
i++;
}

while ((len1 - i) >= 0) {
int result = (str1[len1 - i] - '0') + carry;
char ch = (result % 10) + '0';
str = ch + str;
carry = result / 10;
i++;
}

while ((len2 - i) >= 0) {
int result = (str2[len2 - i] - '0') + carry;
char ch = (result % 10) + '0';
str = ch + str;
carry = result / 10;
i++;
}

if (carry > 0) {
char ch = carry + '0';
str = ch + str;
}

return str;
}

bool checksumUtill(string str, int pos, int str1_len, int str2_len)
{
int n = str.length();
int i = str1_len, j = str2_len;

//if the total sum of the current position and
//both the strings is greater than total length
if (pos + str1_len + str2_len >= n)
return false;

//calculate the sum
string s = add(str.substr(pos, i), str.substr(pos + i, j));

//if the next substring of pos+i+j is equals to the sum
if (s == str.substr(pos + i + j, s.length())) {
if (pos + i + j + s.length() == n)
return true;
return checksumUtill(str, pos + i, j, s.length());
}
return false;
}

bool check_sum_string(string str)
{
if (str.length() == 0)
return false;

int str1_len = 1;
int str2_len = 1;
int pos = 0;

//go for all the combinations
for (int i = 1; i < str.length(); i++) {
for (int j = 1; j < str.length(); j++) {
if (checksumUtill(str, pos, i, j)) {
return true;
}
}
}
return false;
}

int main()
{
int t;

cout << "Test Case : ";
cin >> t;

while (t--) {
string str;
cout << "Enter the String : ";
cin >> str;
if (check_sum_string(str)) {
cout << "It is a sum string\n";
}
else {
cout << "It is not a sum string\n";
}
}
return 0;
}``````

Output

```Test Case : 3
Enter the String : 12345168213
It is a sum string
Enter the String : 123581321
It is a sum string
Enter the String : 15648
It is not a sum string
```