Check if any valid sequence is divisible by M | Java implementation of above approach ; Calculate modulo for this call ; Base case ; check if sum is divisible by M ; check if the current state is already computed ; 1. Try placing ' + ' ; 2. Try placing ' - ' ; calculate value of res for recursive case ; store the value for res for current states and return for parent call ; Driver code ; MAX is the Maximum value M can take
class GFG { static int MAX = 100 ; static int isPossible ( int n , int index , int modulo , int M , int arr [ ] , int dp [ ] [ ] ) { modulo = ( ( modulo % M ) + M ) % M ; if ( index == n ) { if ( modulo == 0 ) { return 1 ; } return 0 ; } if ( dp [ index ] [ modulo ] != - 1 ) { return dp [ index ] [ modulo ] ; } int placeAdd = isPossible ( n , index + 1 , modulo + arr [ index ] , M , arr , dp ) ; int placeMinus = isPossible ( n , index + 1 , modulo - arr [ index ] , M , arr , dp ) ; int res = placeAdd ; dp [ index ] [ modulo ] = res ; return res ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 3 , 4 , 6 } ; int n = arr . length ; int M = 4 ; int dp [ ] [ ] = new int [ n + 1 ] [ MAX ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) { for ( int j = 0 ; j < MAX ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } boolean res ; if ( isPossible ( n , 1 , arr [ 0 ] , M , arr , dp ) == 1 ) { res = true ; } else { res = false ; } System . out . println ( res ? " True " : " False " ) ; } }