Count digit groupings of a number with given constraints | C ++ program to count number of ways to group digits of a number such that sum of digits in every subgroup is less than or equal to its immediate right subgroup . ; Function to find the subgroups ; Terminating Condition ; 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 current position ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countGroups ( int position , int previous_sum , int length , char * num ) { if ( position == length ) return 1 ; int res = 0 ; int sum = 0 ; for ( int i = position ; i < length ; i ++ ) { sum += ( num [ i ] - '0' ) ; if ( sum >= previous_sum ) res += countGroups ( i + 1 , sum , length , num ) ; } return res ; } int main ( ) { char num [ ] = "1119" ; int len = strlen ( num ) ; cout << countGroups ( 0 , 0 , len , num ) ; return 0 ; }