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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 1000 ; bool isPossible ( int n , int index , int sum , int M , int arr [ ] , int dp [ ] [ MAX ] ) { if ( index == n ) { if ( ( sum % M ) == 0 ) return true ; return false ; } if ( dp [ index ] [ sum ] != -1 ) return dp [ index ] [ sum ] ; bool placeAdd = isPossible ( n , index + 1 , sum + arr [ index ] , M , arr , dp ) ; bool placeMinus = isPossible ( n , index + 1 , sum - arr [ index ] , M , arr , dp ) ; bool res = ( placeAdd placeMinus ) ; dp [ index ] [ sum ] = res ; return res ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 6 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int M = 4 ; int dp [ n + 1 ] [ MAX ] ; memset ( dp , -1 , sizeof ( dp ) ) ; bool res ; res = isPossible ( n , 0 , 0 , M , arr , dp ) ; cout << ( res ? " True " : " False " ) << endl ; return 0 ; }