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"
    task = new SubString()
    task.count9SumSubstring(num)

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
• C++
• C#
• Go
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

/*
    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)
	{
		SubString task = new SubString();
		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
		task.count9SumSubstring(num);
	}
}

 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()
{
	SubString *task = new SubString();
	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
	task->count9SumSubstring(num);
	return 0;
}

 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)
	{
		SubString task = new SubString();
		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
		task.count9SumSubstring(num);
	}
}

 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)
}

 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()
{
	$task = new SubString();
	$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
	$task->count9SumSubstring($num);
}
main();

 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 task = new SubString();
	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
	task.count9SumSubstring(num);
}
main();

 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() :
	task = SubString()
	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
	task.count9SumSubstring(num)

if __name__ == "__main__": main()

 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_reader :count
	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() 
	task = SubString.new()
	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
	task.count9SumSubstring(num)
end

main()

 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
		task.count9SumSubstring(num);
	}
}

 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 task: SubString = SubString();
	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
	task.count9SumSubstring(num);
}
main();

 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 task: SubString = SubString();
	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
	task.count9SumSubstring(num);
}

 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.