Count digit groupings of a number with given constraints | Maximum length of input number string ; A memoization table to store results of subproblems length of string is 40 and maximum sum will be 9 * 40 = 360. ; Function to find the count of splits with given condition ; Terminating Condition ; If already evaluated for a given sub problem then return the value ; countGroups for current sub - group is 0 ; sum of digits ; Traverse all digits from current position to rest of the length of string ; If forward_sum is greater than the previous sum , then call the method again ; Note : We pass current sum as previous sum ; total number of subgroups till the current position ; Driver Code
MAX = 40 NEW_LINE dp = [ [ - 1 for i in range ( 9 * MAX + 1 ) ] for i in range ( MAX ) ] NEW_LINE def countGroups ( position , previous_sum , length , num ) : NEW_LINE INDENT if ( position == length ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( dp [ position ] [ previous_sum ] != - 1 ) : NEW_LINE INDENT return dp [ position ] [ previous_sum ] NEW_LINE DEDENT dp [ position ] [ previous_sum ] = 0 NEW_LINE res = 0 NEW_LINE sum = 0 NEW_LINE for i in range ( position , length ) : NEW_LINE INDENT sum += ( ord ( num [ i ] ) - ord ( '0' ) ) NEW_LINE if ( sum >= previous_sum ) : NEW_LINE INDENT res += countGroups ( i + 1 , sum , length , num ) NEW_LINE DEDENT DEDENT dp [ position ] [ previous_sum ] = res NEW_LINE return res NEW_LINE DEDENT num = "1119" NEW_LINE len = len ( num ) NEW_LINE print ( countGroups ( 0 , 0 , len , num ) ) NEW_LINE