Check if a given string is sum-string

Last Updated : 08 Jun, 2025

Given a string s, the task is to determine whether it can be classified as a sum-string.
A string is a sum-string if it can be split into more than two substring such that, the rightmost substring is equal to the sum of the two substrings immediately before it.
This rule must recursively apply to the substring before it.
Note: The rightmost substring should not contain leading zeroes.

Examples:

Input: s = "12243660"
Output: true
Explanation: The string can be split as ["12", "24", "36", "60"] where each number is the sum of the two before it:
36 = 12 + 24, and 60 = 24 + 36. Hence, it is a sum-string.
Input: s = "1111112223"
Output: true
Explanation: Split the string as ["1", "111", "112", "223"], where:
112 = 1 + 111 and 223 = 111 + 112. Hence, it follows the sum-string rule.
Input: s = "123456"
Output: false
Explanation: There is no valid split of the string such that each part satisfies the sum-string property recursively.

Approach:

The idea is to check if the given string is a sum-string, meaning every next number in the string is the sum of the previous two numbers. The thought process starts with trying every possible split of the first two numbers, treating them as starting points. From there, we recursively verify if their sum continues the valid sequence in the string. So, if we fix the lengths of the first two numbers (say len1 and len2), the rest of the string must follow the rule: next number = sum of previous two
We use string-based addition to handle large numbers that may not fit in regular data types.

Step-By-Step Implementation:

Loops through all combinations of len1 and len2 for the first two parts, where len1 and len2 represent lengths of the initial two substrings being considered from string s.
For each combination, call the recursive function checkSequence starting from index 0.
Inside checkSequence, extract part1 and part2 from string s using the given start, len1, and len2.
Call addStrings to compute the sum of part1 and part2 as a string using a digit-wise addition approach.
Compare the resulting sum with the next portion of the string to see if the pattern continues.
If a match is found and the end of the string is reached, return true to indicate a valid sequence.
Otherwise, recursively call checkSequence with updated start, len2, and new length for the expected sum.

C++

// C++ program to check if a string is a  // sum-string using recursion #include <iostream> #include <string> using namespace std; // Adds two numeric strings and returns // the sum as string string addStrings(string num1, string num2) {  if (num1.length() < num2.length()) {  swap(num1, num2);  }  int len1 = num1.length();  int len2 = num2.length();  string sum = "";  int carry = 0;  // Add from least significant digits  for (int i = 0; i < len2; i++) {  int d1 = num1[len1 - 1 - i] - '0';  int d2 = num2[len2 - 1 - i] - '0';  int digit = (d1 + d2 + carry) % 10;  carry = (d1 + d2 + carry) / 10;  sum = char(digit + '0') + sum;  }  // Add remaining digits of num1  for (int i = len2; i < len1; i++) {  int d = num1[len1 - 1 - i] - '0';  int digit = (d + carry) % 10;  carry = (d + carry) / 10;  sum = char(digit + '0') + sum;  }  // Add remaining carry  if (carry) {  sum = char(carry + '0') + sum;  }  return sum; } // Recursively checks if the string from index // start is a valid sum-sequence bool checkSequence(string s, int start, int len1, int len2) {  string part1 = s.substr(start, len1);  string part2 = s.substr(start + len1, len2);  // Check for leading zeroes  if ((part1.length() > 1 && part1[0] == '0') ||  (part2.length() > 1 && part2[0] == '0')) {  return false;  }  string expectedSum = addStrings(part1, part2);  int sumLen = expectedSum.length();  // If sum length exceeds remaining string,  // return false  if (start + len1 + len2 + sumLen > s.length()) {  return false;  }  string nextPart = s.substr(start + len1 + len2, sumLen);  // Check for leading zeroes  if (nextPart.length() > 1 && nextPart[0] == '0') {  return false;  }  // If the sum matches the next part in string  if (expectedSum == nextPart) {  // If end is reached, return true  if (start + len1 + len2 + sumLen == s.length()) {  return true;  }  // Recur for next pair: part2 and expectedSum  return checkSequence(s, start + len1, len2, sumLen);  }  // Sum does not match the next segment  return false; } // Function to check if a string is a sum-string bool isSumString(string &s) {  int n = s.length();  // Try all combinations of first two parts  for (int len1 = 1; len1 < n; len1++) {  for (int len2 = 1; len1 + len2 < n; len2++) {  if (checkSequence(s, 0, len1, len2)) {  return true;  }  }  }  return false; } // Driver Code int main() {    string s = "12243660";    cout << (isSumString(s)?"true":"false"); }

Java

// Java program to check if a string is a  // sum-string using recursion class GfG {  // Adds two numeric strings and returns   // the sum as string  static String addStrings(String num1, String num2) {    if (num1.length() < num2.length()) {  String temp = num1;  num1 = num2;  num2 = temp;  }  int len1 = num1.length();  int len2 = num2.length();  String sum = "";  int carry = 0;  // Add from least significant digits  for (int i = 0; i < len2; i++) {  int d1 = num1.charAt(len1 - 1 - i) - '0';  int d2 = num2.charAt(len2 - 1 - i) - '0';  int digit = (d1 + d2 + carry) % 10;  carry = (d1 + d2 + carry) / 10;  sum = (char)(digit + '0') + sum;  }  // Add remaining digits of num1  for (int i = len2; i < len1; i++) {  int d = num1.charAt(len1 - 1 - i) - '0';  int digit = (d + carry) % 10;  carry = (d + carry) / 10;  sum = (char)(digit + '0') + sum;  }  // Add remaining carry  if (carry > 0) {  sum = (char)(carry + '0') + sum;  }  return sum;  }  // Recursively checks if the string from index   // start is a valid sum-sequence  static boolean checkSequence(String s, int start,   int len1, int len2) {  String part1 = s.substring(start, start + len1);  String part2 = s.substring(start + len1, start + len1 + len2);  // Leading zero check  if ((part1.length() > 1 && part1.charAt(0) == '0') ||  (part2.length() > 1 && part2.charAt(0) == '0')) {  return false;  }  String expectedSum = addStrings(part1, part2);  int sumLen = expectedSum.length();  // If sum length exceeds remaining string,   // return false  if (start + len1 + len2 + sumLen > s.length()) {  return false;  }  String part3 = s.substring(start + len1 + len2, start + len1 + len2 + sumLen);  // Leading zero check for sum part  if (part3.length() > 1 && part3.charAt(0) == '0') {  return false;  }  // If the sum matches the next part in string  if (expectedSum.equals(part3)) {    // If end is reached, return true  if (start + len1 + len2 + sumLen == s.length()) {  return true;  }  // Recur for next pair: part2 and expectedSum  return checkSequence(s, start + len1, len2, sumLen);  }  // Sum does not match the next segment  return false;  }  // Function to check if a string is a sum-string  static boolean isSumString(String s) {  int n = s.length();  // Try all combinations of first two parts  for (int len1 = 1; len1 < n; len1++) {  for (int len2 = 1; len1 + len2 < n; len2++) {  if (checkSequence(s, 0, len1, len2)) {  return true;  }  }  }  return false;  }  // Driver Code  public static void main(String[] args) {  String s = "12243660";  System.out.println(isSumString(s));  } }

Python

# Python program to check if a string is a  # sum-string using recursion # Adds two numeric strings and returns  # the sum as string def addStrings(num1, num2): if len(num1) < len(num2): num1, num2 = num2, num1 len1 = len(num1) len2 = len(num2) sum = "" carry = 0 # Add from least significant digits for i in range(len2): d1 = ord(num1[len1 - 1 - i]) - ord('0') d2 = ord(num2[len2 - 1 - i]) - ord('0') digit = (d1 + d2 + carry) % 10 carry = (d1 + d2 + carry) // 10 sum = chr(digit + ord('0')) + sum # Add remaining digits of num1 for i in range(len2, len1): d = ord(num1[len1 - 1 - i]) - ord('0') digit = (d + carry) % 10 carry = (d + carry) // 10 sum = chr(digit + ord('0')) + sum # Add remaining carry if carry: sum = chr(carry + ord('0')) + sum return sum # Recursively checks if the string from index  # start is a valid sum-sequence def checkSequence(s, start, len1, len2): part1 = s[start:start + len1] part2 = s[start + len1:start + len1 + len2] # Leading zero check if (len(part1) > 1 and part1[0] == '0') or (len(part2) > 1 and part2[0] == '0'): return False expectedSum = addStrings(part1, part2) sumLen = len(expectedSum) # If sum length exceeds remaining string,  # return false if start + len1 + len2 + sumLen > len(s): return False part3 = s[start + len1 + len2:start + len1 + len2 + sumLen] # Leading zero check for sum part if len(part3) > 1 and part3[0] == '0': return False # If the sum matches the next part in string if expectedSum == s[start + len1 + len2: start + len1 + len2 + sumLen]: # If end is reached, return true if start + len1 + len2 + sumLen == len(s): return True # Recur for next pair: part2 and expectedSum return checkSequence(s, start + len1, len2, sumLen) # Sum does not match the next segment return False # Function to check if a string is a sum-string def isSumString(s): n = len(s) # Try all combinations of first two parts for len1 in range(1, n): for len2 in range(1, n - len1): if checkSequence(s, 0, len1, len2): return True return False # Driver Code if __name__ == "__main__": s = "12243660" print("true" if isSumString(s) else "false")

// C# program to check if a string is a  // sum-string using recursion using System; class GfG {  // Adds two numeric strings and returns   // the sum as string  static string addStrings(string num1, string num2) {    if (num1.Length < num2.Length) {  var temp = num1;  num1 = num2;  num2 = temp;  }  int len1 = num1.Length;  int len2 = num2.Length;  string sum = "";  int carry = 0;  // Add from least significant digits  for (int i = 0; i < len2; i++) {  int d1 = num1[len1 - 1 - i] - '0';  int d2 = num2[len2 - 1 - i] - '0';  int digit = (d1 + d2 + carry) % 10;  carry = (d1 + d2 + carry) / 10;  sum = (char)(digit + '0') + sum;  }  // Add remaining digits of num1  for (int i = len2; i < len1; i++) {  int d = num1[len1 - 1 - i] - '0';  int digit = (d + carry) % 10;  carry = (d + carry) / 10;  sum = (char)(digit + '0') + sum;  }  // Add remaining carry  if (carry > 0) {  sum = (char)(carry + '0') + sum;  }  return sum;  }  // Recursively checks if the string from index   // start is a valid sum-sequence  static bool checkSequence(string s, int start,   int len1, int len2) {  string part1 = s.Substring(start, len1);  string part2 = s.Substring(start + len1, len2);  // Leading zero check  if ((part1.Length > 1 && part1[0] == '0') ||   (part2.Length > 1 && part2[0] == '0')) {  return false;  }  string expectedSum = addStrings(part1, part2);  int sumLen = expectedSum.Length;  // If sum length exceeds remaining string,   // return false  if (start + len1 + len2 + sumLen > s.Length) {  return false;  }  string part3 = s.Substring(start + len1 + len2, sumLen);  // Leading zero check for sum part  if (part3.Length > 1 && part3[0] == '0') {  return false;  }  // If the sum matches the next part in string  if (expectedSum == s.Substring(start +   len1 + len2, sumLen)) {    // If end is reached, return true  if (start + len1 + len2 + sumLen == s.Length) {  return true;  }  // Recur for next pair: part2 and expectedSum  return checkSequence(s, start + len1, len2, sumLen);  }  // Sum does not match the next segment  return false;  }  // Function to check if a string is a sum-string  static bool isSumString(string s) {  int n = s.Length;  // Try all combinations of first two parts  for (int len1 = 1; len1 < n; len1++) {  for (int len2 = 1; len1 + len2 < n; len2++) {  if (checkSequence(s, 0, len1, len2)) {  return true;  }  }  }  return false;  }  // Driver Code  static void Main() {  string s = "12243660";  Console.WriteLine((isSumString(s)?"true":"false"));  } }

JavaScript

// JavaScript program to check if a string is a  // sum-string using recursion // Adds two numeric strings and returns  // the sum as string function addStrings(num1, num2) {  if (num1.length < num2.length) {  [num1, num2] = [num2, num1];  }  let len1 = num1.length;  let len2 = num2.length;  let sum = "";  let carry = 0;  // Add from least significant digits  for (let i = 0; i < len2; i++) {  let d1 = num1.charCodeAt(len1 - 1 - i) - 48;  let d2 = num2.charCodeAt(len2 - 1 - i) - 48;  let digit = (d1 + d2 + carry) % 10;  carry = Math.floor((d1 + d2 + carry) / 10);  sum = String.fromCharCode(digit + 48) + sum;  }  // Add remaining digits of num1  for (let i = len2; i < len1; i++) {  let d = num1.charCodeAt(len1 - 1 - i) - 48;  let digit = (d + carry) % 10;  carry = Math.floor((d + carry) / 10);  sum = String.fromCharCode(digit + 48) + sum;  }  // Add remaining carry  if (carry > 0) {  sum = String.fromCharCode(carry + 48) + sum;  }  return sum; } // Recursively checks if the string from index  // start is a valid sum-sequence function checkSequence(s, start, len1, len2) {  let part1 = s.substring(start, start + len1);  let part2 = s.substring(start + len1, start + len1 + len2);  // Leading zero check  if ((part1.length > 1 && part1[0] === '0') ||   (part2.length > 1 && part2[0] === '0')) {  return false;  }  let expectedSum = addStrings(part1, part2);  let sumLen = expectedSum.length;  // If sum length exceeds remaining string,   // return false  if (start + len1 + len2 + sumLen > s.length) {  return false;  }  let part3 = s.substring(start + len1 + len2, start + len1 + len2 + sumLen);  // Leading zero check for sum part  if (part3.length > 1 && part3[0] === '0') {  return false;  }  // If the sum matches the next part in string  if (expectedSum === s.substring(start +   len1 + len2, start +   len1 + len2 + sumLen)) {  // If end is reached, return true  if (start + len1 + len2 + sumLen === s.length) {  return true;  }  // Recur for next pair: part2 and expectedSum  return checkSequence(s, start + len1, len2, sumLen);  }  // Sum does not match the next segment  return false; } // Function to check if a string is a sum-string function isSumString(s) {  let n = s.length;  // Try all combinations of first two parts  for (let len1 = 1; len1 < n; len1++) {  for (let len2 = 1; len1 + len2 < n; len2++) {  if (checkSequence(s, 0, len1, len2)) {  return true;  }  }  }  return false; } // Driver Code let s = "12243660"; console.log(isSumString(s));

Output

true

Time Complexity: O(n^3), due to trying all O(n²) prefix combinations and doing O(n) string addition/comparisons recursively.
Space Complexity: O(n), for storing temporary substrings and the sum result.