Check if any valid sequence is divisible by M | C # program to check if any valid sequence is divisible by M ; 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
using System ; class GFG { static int MAX = 1000 ; static Boolean isPossible ( int n , int index , int sum , int M , int [ ] arr , int [ , ] dp ) { if ( index == n ) { if ( ( sum % M ) == 0 ) return true ; return false ; } else if ( sum < 0 sum >= MAX ) return false ; if ( dp [ index , sum ] != - 1 ) { if ( dp [ index , sum ] == 0 ) return false ; return true ; } Boolean placeAdd = isPossible ( n , index + 1 , sum + arr [ index ] , M , arr , dp ) ; Boolean placeMinus = isPossible ( n , index + 1 , sum - arr [ index ] , M , arr , dp ) ; Boolean res = ( placeAdd placeMinus ) ; dp [ index , sum ] = ( res ) ? 1 : 0 ; 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 ; res = isPossible ( n , 0 , 0 , M , arr , dp ) ; Console . WriteLine ( ( res ? " True " : " False " ) ) ; } }