Posted on by Kalkicode
Code Recursion

# Number of substrings which recursively add up to 9

The problem is to find the total number of substrings in a given numeric string that recursively add up to 9. We are given a numeric string, and we need to count all the possible substrings such that their individual digits add up to 9. The substrings can be of any length, and they do not need to be consecutive. We can consider single digits as substrings as well if they are equal to 9.

## Problem Statement with Example

Let's understand the problem with the given example and how the count is derived step by step:

Given numeric string: "35192169"

``````
num =  35192169
// ----------------
9        --> ➀   9
2169     --> ➁   [2+1+6+9]   => [18] => [1+9] = 9
92169    --> ➂   [9+2+1+6+9] => [27] => [2+7] = 9
35192169 --> ➃   [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
216      --> ➄   [2+1+6] = 9
9216     --> ➅   [9+2+1+6] => [18] => [1+8] = 9
3519216  --> ➆   [3+5+1+9+2+1+6] => [27] => [2+7] = 9
51921    --> ➇   [5+1+9+2+1] => [18] => [1+8] = 9
9        --> ➈   9
3519     --> ➉   [3+5+1+9] => [18] => [1+8] = 9
351      --> ⑪   [3+5+1] = 9
// --------------
Result = 11
``````
1. Substring "9": The individual digit "9" is equal to 9. So, we count it as one valid substring. Count = 1.

2. Substring "2169": The digits in this substring add up to 9 (2 + 1 + 6 + 9 = 18, and 1 + 8 = 9). Count = 2.

3. Substring "92169": The digits in this substring add up to 9 (9 + 2 + 1 + 6 + 9 = 27, and 2 + 7 = 9). Count = 3.

4. Substring "35192169": The digits in this substring add up to 9 (3 + 5 + 1 + 9 + 2 + 1 + 6 + 9 = 36, and 3 + 6 = 9). Count = 4.

5. Substring "216": The digits in this substring add up to 9 (2 + 1 + 6 = 9). Count = 5.

6. Substring "9216": The digits in this substring add up to 9 (9 + 2 + 1 + 6 = 18, and 1 + 8 = 9). Count = 6.

7. Substring "3519216": The digits in this substring add up to 9 (3 + 5 + 1 + 9 + 2 + 1 + 6 = 27, and 2 + 7 = 9). Count = 7.

8. Substring "51921": The digits in this substring add up to 9 (5 + 1 + 9 + 2 + 1 = 18, and 1 + 8 = 9). Count = 8.

9. Substring "9": Another occurrence of a single digit "9" as a valid substring. Count = 9.

10. Substring "3519": The digits in this substring add up to 9 (3 + 5 + 1 + 9 = 18, and 1 + 8 = 9). Count = 10.

11. Substring "351": The digits in this substring add up to 9 (3 + 5 + 1 = 9). Count = 11.

## Pseudocode and Algorithm

To solve this problem, we can use a recursive approach. The recursive function will iterate through the string and check for valid substrings that add up to 9.

Pseudocode:

``````
count = 0

function find9Sum(num, sum, index, n):
if sum != 0 and (sum % 9) == 0:
count += 1

if index < 0:
return

find9Sum(num, sum + (num.charAt(index) - '0'), index - 1, n)

if index == 0 and n > 1:
find9Sum(num, 0, n - 1, n - 1)

n = length(num)
count = 0
find9Sum(num, 0, n - 1, n - 1)

print "Given num : " + num
print "Total Result : " + count

procedure main():
num = "35192169"

main()
``````

## Explanation of the Algorithm

1. We initialize a variable `count` to 0 to keep track of the number of substrings that add up to 9.

2. The `find9Sum` function takes four parameters: `num` (the numeric string), `sum` (the sum of digits in the current substring), `index` (the current index being considered), and `n` (the total length of the string).

3. Within the `find9Sum` function:

• If the `sum` is not zero and the sum modulo 9 is zero, we increment the `count` as we have found a valid substring.
• If the `index` is less than 0, we have considered all possible substrings for the current recursion path, so we return.
• Otherwise, we recursively call the `find9Sum` function with updated parameters:
• Increment the `sum` with the digit at the current index (`num[index] - '0'`) to consider the current digit in the sum.
• Decrement the `index` to consider the next digit in the substring.
• If we have reached the first digit (index == 0) and `n` (length of the original string) is greater than 1, we make a recursive call with the index as `n - 1` to start a new recursion path.
4. The `count9SumSubstring` function takes the numeric string `num` as input and initializes the `count` to 0. It then calls the `find9Sum` function with the initial parameters to start the recursive process.

5. Finally, after the recursion is completed, it prints the original string and the final `count` of valid substrings.

## Program Solution

``````/*
Java program for
Number of substrings which recursively add up to 9
*/
public class SubString
{
public int count;
public SubString()
{
this.count = 0;
}
public void find9Sum(String num, int sum, int index, int n)
{
if (sum != 0 && (sum % 9) == 0)
{
this.count++;
}
if (index < 0)
{
return;
}
find9Sum(num, sum + (num.charAt(index) - '0'), index - 1, n);
if (index == 0 && n > 1)
{
// Recursively find other substring which sum up to 9
find9Sum(num, 0, n - 1, n - 1);
}
}
public void count9SumSubstring(String num)
{
int n = num.length();
this.count = 0;
find9Sum(num, 0, n - 1, n - 1);
// Display given number
System.out.println(" Given num : " + num);
// Display calculated result
System.out.println(" Total Result : " + this.count);
}
public static void main(String[] args)
{
String num = "35192169";
// num =  35192169
// ----------------
// 9        --> ➀   9
// 2169     --> ➁   [2+1+6+9]   => [18] => [1+9] = 9
// 92169    --> ➂   [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃   [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216      --> ➄   [2+1+6] = 9
// 9216     --> ➅   [9+2+1+6] => [18] => [1+8] = 9
// 3519216  --> ➆   [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921    --> ➇   [5+1+9+2+1] => [18] => [1+8] = 9
// 9        --> ➈   9
// 3519     --> ➉   [3+5+1+9] => [18] => [1+8] = 9
// 351      --> ⑪   [3+5+1] = 9
// --------------
// Result = 11
}
}``````

#### Output

`````` Given num : 35192169
Total Result : 11``````
``````// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
C++ program for
Number of substrings which recursively add up to 9
*/
class SubString
{
public: int count;
SubString()
{
this->count = 0;
}
void find9Sum(string num, int sum, int index, int n)
{
if (sum != 0 && (sum % 9) == 0)
{
this->count++;
}
if (index < 0)
{
return;
}
this->find9Sum(num, sum + (num[index] - '0'), index - 1, n);

if (index == 0 && n > 1)
{
// Recursively find other substring which sum up to 9
this->find9Sum(num, 0, n - 1, n - 1);
}
}
void count9SumSubstring(string num)
{
int n = num.length();
this->count = 0;
this->find9Sum(num, 0, n - 1, n - 1);
// Display given number
cout << " Given num : " << num << endl;
// Display calculated result
cout << " Total Result : " << this->count << endl;
}
};
int main()
{
string num = "35192169";
// num =  35192169
// ----------------
// 9        --> ➀   9
// 2169     --> ➁   [2+1+6+9]   => [18] => [1+9] = 9
// 92169    --> ➂   [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃   [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216      --> ➄   [2+1+6] = 9
// 9216     --> ➅   [9+2+1+6] => [18] => [1+8] = 9
// 3519216  --> ➆   [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921    --> ➇   [5+1+9+2+1] => [18] => [1+8] = 9
// 9        --> ➈   9
// 3519     --> ➉   [3+5+1+9] => [18] => [1+8] = 9
// 351      --> ⑪   [3+5+1] = 9
// --------------
// Result = 11
return 0;
}``````

#### Output

`````` Given num : 35192169
Total Result : 11``````
``````// Include namespace system
using System;
/*
Csharp program for
Number of substrings which recursively add up to 9
*/
public class SubString
{
public int count;
public SubString()
{
this.count = 0;
}
public void find9Sum(String num, int sum, int index, int n)
{
if (sum != 0 && (sum % 9) == 0)
{
this.count++;
}
if (index < 0)
{
return;
}
this.find9Sum(num, sum + (num[index] - '0'), index - 1, n);
if (index == 0 && n > 1)
{
// Recursively find other substring which sum up to 9
this.find9Sum(num, 0, n - 1, n - 1);
}
}
public void count9SumSubstring(String num)
{
int n = num.Length;
this.count = 0;
this.find9Sum(num, 0, n - 1, n - 1);
// Display given number
Console.WriteLine(" Given num : " + num);
// Display calculated result
Console.WriteLine(" Total Result : " + this.count);
}
public static void Main(String[] args)
{
String num = "35192169";
// num =  35192169
// ----------------
// 9        --> ➀   9
// 2169     --> ➁   [2+1+6+9]   => [18] => [1+9] = 9
// 92169    --> ➂   [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃   [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216      --> ➄   [2+1+6] = 9
// 9216     --> ➅   [9+2+1+6] => [18] => [1+8] = 9
// 3519216  --> ➆   [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921    --> ➇   [5+1+9+2+1] => [18] => [1+8] = 9
// 9        --> ➈   9
// 3519     --> ➉   [3+5+1+9] => [18] => [1+8] = 9
// 351      --> ⑪   [3+5+1] = 9
// --------------
// Result = 11
}
}``````

#### Output

`````` Given num : 35192169
Total Result : 11``````
``````package main
import "fmt"
/*
Go program for
Number of substrings which recursively add up to 9
*/

func find9Sum(num string,count *int, sum int, index int, n int) {
if sum != 0 && (sum % 9) == 0 {
*count+=1
}
if index < 0 {
return
}
find9Sum(num,
count,
sum + (int(num[index]) - 48),
index - 1, n)
if index == 0 && n > 1 {
// Recursively find other substring which sum up to 9
find9Sum(num,count, 0, n - 1, n - 1)
}
}
func count9SumSubstring(num string) {
var n int = len(num)
var count int = 0
find9Sum(num,&count, 0, n - 1, n - 1)
// Display given number
fmt.Println(" Given num : ", num)
// Display calculated result
fmt.Println(" Total Result : ", count)
}
func main() {

var num string = "35192169"
// num =  35192169
// ----------------
// 9        --> ➀   9
// 2169     --> ➁   [2+1+6+9]   => [18] => [1+9] = 9
// 92169    --> ➂   [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃   [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216      --> ➄   [2+1+6] = 9
// 9216     --> ➅   [9+2+1+6] => [18] => [1+8] = 9
// 3519216  --> ➆   [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921    --> ➇   [5+1+9+2+1] => [18] => [1+8] = 9
// 9        --> ➈   9
// 3519     --> ➉   [3+5+1+9] => [18] => [1+8] = 9
// 351      --> ⑪   [3+5+1] = 9
// --------------
// Result = 11
count9SumSubstring(num)
}``````

#### Output

`````` Given num : 35192169
Total Result : 11``````
``````<?php
/*
Php program for
Number of substrings which recursively add up to 9
*/
class SubString
{
public \$count;
public	function __construct()
{
\$this->count = 0;
}
public	function find9Sum(\$num, \$sum, \$index, \$n)
{
if (\$sum != 0 && (\$sum % 9) == 0)
{
\$this->count++;
}
if (\$index < 0)
{
return;
}
\$this->find9Sum(\$num, \$sum +
(ord(\$num[\$index]) -
ord('0')), \$index - 1, \$n);
if (\$index == 0 && \$n > 1)
{
// Recursively find other substring which sum up to 9
\$this->find9Sum(\$num, 0, \$n - 1, \$n - 1);
}
}
public	function count9SumSubstring(\$num)
{
\$n = strlen(\$num);
\$this->count = 0;
\$this->find9Sum(\$num, 0, \$n - 1, \$n - 1);
// Display given number
echo(" Given num : ".\$num."\n");
// Display calculated result
echo(" Total Result : ".\$this->count."\n");
}
}

function main()
{
\$num = "35192169";
// num =  35192169
// ----------------
// 9        --> ➀   9
// 2169     --> ➁   [2+1+6+9]   => [18] => [1+9] = 9
// 92169    --> ➂   [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃   [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216      --> ➄   [2+1+6] = 9
// 9216     --> ➅   [9+2+1+6] => [18] => [1+8] = 9
// 3519216  --> ➆   [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921    --> ➇   [5+1+9+2+1] => [18] => [1+8] = 9
// 9        --> ➈   9
// 3519     --> ➉   [3+5+1+9] => [18] => [1+8] = 9
// 351      --> ⑪   [3+5+1] = 9
// --------------
// Result = 11
}
main();``````

#### Output

`````` Given num : 35192169
Total Result : 11``````
``````/*
Node JS program for
Number of substrings which recursively add up to 9
*/
class SubString
{
constructor()
{
this.count = 0;
}
find9Sum(num, sum, index, n)
{
if (sum != 0 && (sum % 9) == 0)
{
this.count++;
}
if (index < 0)
{
return;
}
this.find9Sum(num, sum +
(num.charCodeAt(index) -
'0'.charCodeAt(0)), index - 1, n);
if (index == 0 && n > 1)
{
// Recursively find other substring which sum up to 9
this.find9Sum(num, 0, n - 1, n - 1);
}
}
count9SumSubstring(num)
{
var n = num.length;
this.count = 0;
this.find9Sum(num, 0, n - 1, n - 1);
// Display given number
console.log(" Given num : " + num);
// Display calculated result
console.log(" Total Result : " + this.count);
}
}

function main()
{
var num = "35192169";
// num =  35192169
// ----------------
// 9        --> ➀   9
// 2169     --> ➁   [2+1+6+9]   => [18] => [1+9] = 9
// 92169    --> ➂   [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃   [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216      --> ➄   [2+1+6] = 9
// 9216     --> ➅   [9+2+1+6] => [18] => [1+8] = 9
// 3519216  --> ➆   [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921    --> ➇   [5+1+9+2+1] => [18] => [1+8] = 9
// 9        --> ➈   9
// 3519     --> ➉   [3+5+1+9] => [18] => [1+8] = 9
// 351      --> ⑪   [3+5+1] = 9
// --------------
// Result = 11
}
main();``````

#### Output

`````` Given num : 35192169
Total Result : 11``````
``````#    Python 3 program for
#    Number of substrings which recursively add up to 9
class SubString :
def __init__(self) :
self.count = 0

def find9Sum(self, num, sum, index, n) :
if (sum != 0 and(sum % 9) == 0) :
self.count += 1

if (index < 0) :
return

self.find9Sum(num, sum +
(ord(num[index]) - ord('0')), index - 1, n)
if (index == 0 and n > 1) :
#  Recursively find other substring which sum up to 9
self.find9Sum(num, 0, n - 1, n - 1)

def count9SumSubstring(self, num) :
n = len(num)
self.count = 0
self.find9Sum(num, 0, n - 1, n - 1)
#  Display given number
print(" Given num : ", num)
#  Display calculated result
print(" Total Result : ", self.count)

def main() :
num = "35192169"
#  num =  35192169
#  ----------------
#  9        --> ➀   9
#  2169     --> ➁   [2+1+6+9]   => [18] => [1+9] = 9
#  92169    --> ➂   [9+2+1+6+9] => [27] => [2+7] = 9
#  35192169 --> ➃   [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
#  216      --> ➄   [2+1+6] = 9
#  9216     --> ➅   [9+2+1+6] => [18] => [1+8] = 9
#  3519216  --> ➆   [3+5+1+9+2+1+6] => [27] => [2+7] = 9
#  51921    --> ➇   [5+1+9+2+1] => [18] => [1+8] = 9
#  9        --> ➈   9
#  3519     --> ➉   [3+5+1+9] => [18] => [1+8] = 9
#  351      --> ⑪   [3+5+1] = 9
#  --------------
#  Result = 11

if __name__ == "__main__": main()``````

#### Output

`````` Given num :  35192169
Total Result :  11``````
``````#    Ruby program for
#    Number of substrings which recursively add up to 9
class SubString
# Define the accessor and reader of class SubString
attr_accessor :count
def initialize()
self.count = 0
end

def find9Sum(num, sum, index, n)
if (sum != 0 && (sum % 9) == 0)
self.count += 1
end

if (index < 0)
return
end

self.find9Sum(num, sum + (num[index].ord - '0'.ord), index - 1, n)
if (index == 0 && n > 1)
#  Recursively find other substring which sum up to 9
self.find9Sum(num, 0, n - 1, n - 1)
end

end

def count9SumSubstring(num)
n = num.length
self.count = 0
self.find9Sum(num, 0, n - 1, n - 1)
#  Display given number
print(" Given num : ", num, "\n")
#  Display calculated result
print(" Total Result : ", self.count, "\n")
end

end

def main()
num = "35192169"
#  num =  35192169
#  ----------------
#  9        --> ➀   9
#  2169     --> ➁   [2+1+6+9]   => [18] => [1+9] = 9
#  92169    --> ➂   [9+2+1+6+9] => [27] => [2+7] = 9
#  35192169 --> ➃   [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
#  216      --> ➄   [2+1+6] = 9
#  9216     --> ➅   [9+2+1+6] => [18] => [1+8] = 9
#  3519216  --> ➆   [3+5+1+9+2+1+6] => [27] => [2+7] = 9
#  51921    --> ➇   [5+1+9+2+1] => [18] => [1+8] = 9
#  9        --> ➈   9
#  3519     --> ➉   [3+5+1+9] => [18] => [1+8] = 9
#  351      --> ⑪   [3+5+1] = 9
#  --------------
#  Result = 11
end

main()``````

#### Output

`````` Given num : 35192169
Total Result : 11
``````
``````/*
Scala program for
Number of substrings which recursively add up to 9
*/
class SubString(var count: Int)
{
def this()
{
this(0);
}
def find9Sum(
num: String,
sum: Int,
index: Int,
n: Int): Unit = {
if (sum != 0 && (sum % 9) == 0)
{
this.count += 1;
}
if (index < 0)
{
return;
}
find9Sum(num, sum +
(num.charAt(index).toInt - '0'.toInt), index - 1, n);
if (index == 0 && n > 1)
{
// Recursively find other substring which sum up to 9
find9Sum(num, 0, n - 1, n - 1);
}
}
def count9SumSubstring(num: String): Unit = {
var n: Int = num.length();
this.count = 0;
find9Sum(num, 0, n - 1, n - 1);
// Display given number
println(" Given num : " + num);
// Display calculated result
println(" Total Result : " + this.count);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SubString = new SubString();
var num: String = "35192169";
// num =  35192169
// ----------------
// 9        --> ➀   9
// 2169     --> ➁   [2+1+6+9]   => [18] => [1+9] = 9
// 92169    --> ➂   [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃   [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216      --> ➄   [2+1+6] = 9
// 9216     --> ➅   [9+2+1+6] => [18] => [1+8] = 9
// 3519216  --> ➆   [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921    --> ➇   [5+1+9+2+1] => [18] => [1+8] = 9
// 9        --> ➈   9
// 3519     --> ➉   [3+5+1+9] => [18] => [1+8] = 9
// 351      --> ⑪   [3+5+1] = 9
// --------------
// Result = 11
}
}``````

#### Output

`````` Given num : 35192169
Total Result : 11``````
``````import Foundation;
/*
Swift 4 program for
Number of substrings which recursively add up to 9
*/
class SubString
{
var count: Int;
init()
{
self.count = 0;
}
func find9Sum(_ num: [Character],
_ sum: Int,
_ index: Int,
_ n: Int)
{
if (sum  != 0 && (sum % 9) == 0)
{
self.count += 1;
}
if (index < 0)
{
return;
}
self.find9Sum(num, sum +
(Int(UnicodeScalar(String(num[index]))!.value) -
Int(UnicodeScalar(String("0"))!.value)), index - 1, n);
if (index == 0 && n > 1)
{
// Recursively find other substring which sum up to 9
self.find9Sum(num, 0, n - 1, n - 1);
}
}
func count9SumSubstring(_ num: String)
{
let n: Int = num.count;
self.count = 0;
self.find9Sum(Array(num), 0, n - 1, n - 1);
// Display given number
print(" Given num : ", num);
// Display calculated result
print(" Total Result : ", self.count);
}
}
func main()
{
let num: String = "35192169";
// num =  35192169
// ----------------
// 9        --> ➀   9
// 2169     --> ➁   [2+1+6+9]   => [18] => [1+9] = 9
// 92169    --> ➂   [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃   [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216      --> ➄   [2+1+6] = 9
// 9216     --> ➅   [9+2+1+6] => [18] => [1+8] = 9
// 3519216  --> ➆   [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921    --> ➇   [5+1+9+2+1] => [18] => [1+8] = 9
// 9        --> ➈   9
// 3519     --> ➉   [3+5+1+9] => [18] => [1+8] = 9
// 351      --> ⑪   [3+5+1] = 9
// --------------
// Result = 11
}
main();``````

#### Output

`````` Given num :  35192169
Total Result :  11``````
``````/*
Kotlin program for
Number of substrings which recursively add up to 9
*/
class SubString
{
var count: Int;
constructor()
{
this.count = 0;
}
fun find9Sum(num: String, sum: Int, index: Int, n: Int): Unit
{
if (sum != 0 && (sum % 9) == 0)
{
this.count += 1;
}
if (index < 0)
{
return;
}
this.find9Sum(num, sum +
(num.get(index).toInt() - '0'.toInt()),
index - 1, n);
if (index == 0 && n > 1)
{
// Recursively find other substring which sum up to 9
this.find9Sum(num, 0, n - 1, n - 1);
}
}
fun count9SumSubstring(num: String): Unit
{
val n: Int = num.length;
this.count = 0;
this.find9Sum(num, 0, n - 1, n - 1);
// Display given number
println(" Given num : " + num);
// Display calculated result
println(" Total Result : " + this.count);
}
}
fun main(args: Array < String > ): Unit
{
val num: String = "35192169";
// num =  35192169
// ----------------
// 9        --> ➀   9
// 2169     --> ➁   [2+1+6+9]   => [18] => [1+9] = 9
// 92169    --> ➂   [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃   [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216      --> ➄   [2+1+6] = 9
// 9216     --> ➅   [9+2+1+6] => [18] => [1+8] = 9
// 3519216  --> ➆   [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921    --> ➇   [5+1+9+2+1] => [18] => [1+8] = 9
// 9        --> ➈   9
// 3519     --> ➉   [3+5+1+9] => [18] => [1+8] = 9
// 351      --> ⑪   [3+5+1] = 9
// --------------
// Result = 11
}``````

#### Output

`````` Given num : 35192169
Total Result : 11``````

## Resultant Output Explanation

In the given example, we used the input string "35192169". The algorithm processed the string as described above, and after completion, it printed the original string and the total result, which is 11. This indicates that there are 11 substrings in the given numeric string that recursively add up to 9.

## Time Complexity

The time complexity of the provided algorithm is O(2^n), where n is the length of the input numeric string. This is because the recursive function explores all possible combinations of substrings. For each digit, it has two choices: either include it in the current substring or start a new substring. As a result, the number of recursive calls grows exponentially with the length of the string. This makes the algorithm inefficient for large input strings. To optimize the solution further, we can use dynamic programming or memoization to avoid redundant calculations and reduce the time complexity.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post