Given an array of N integers, using ‘+’ and ‘-‘ between the elements if there is a way to form a of numbers which evaluate to a number by M

Examples:

```Input : arr = {1, 2, 3, 4, 6}
M = 4
Output : True,
There is a valid sequence i. e., (1 - 2
+ 3 + 4 + 6), which evaluates to 12 that
is divisible by 4

Input : arr = {1, 3, 9}
M = 2
Output : False
There is no sequence which evaluates to
a number divisible by M.
```

A simple solution is to recursively consider all possible scenarios ie either use a ;+’ or a ‘-‘ operator between the elements and maintain a variable sum which stores the result.If this result is divisible by M then return true else return false
Recursive implementation is as follows:

```bool isPossible(int index, int sum)
{
// Base case
if (index == n) {

// check if sum is divisible by M
if ((sum % M) == 0)
return true;
return false;
}

// recursively call by considering '+'
// or '-' between index and index+1

// 1.Try placing '+'
bool placeAdd = isPossible(index + 1,
sum + arr[index]);

// 2. Try placing '-'
bool placeMinus = isPossible(index + 1,
sum - arr[index]);

return true;

return false;
}
```

There are overlapping subproblems as shown in the image below (Note: the image represents the recursion tree till index = 3)

So, now we will solve this using dynamic programming

Method 1:
We apply Dynamic Programming with two states :-
(i) index,
(ii) sum
So DP[index][sum] stores the current index we are at and sum stores the result of evaluation of the sequence formed till that index.

```#include <bits/stdc++.h>
using namespace std;

const int MAX = 1000;

bool isPossible(int n, int index, int sum,
int M, int arr[], int dp[][MAX])
{

// Base case
if (index == n) {

// check if sum is divisible by M
if ((sum % M) == 0)
return true;
return false;
}

// check if the current state
if (dp[index][sum] != -1)
return dp[index][sum];

// 1.Try placing '+'
bool placeAdd = isPossible(n, index + 1,
sum + arr[index], M, arr, dp);

// 2. Try placing '-'
bool placeMinus = isPossible(n, index + 1,
sum - arr[index], M, arr, dp);

// calculate value of res for recursive case
bool res = (placeAdd || placeMinus);

// store the value for res for current
// states and return for parent call
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;
}
```

The Complexity of this method is O(N*sum) where sum is the maximum possible sum for the sequence of integers and N is the number of elements in the array.

Method 2(efficient):
This is more efficient than Method 1. Here also, we apply Dynamic Programming but with two different states :-
(i) index,
(ii) modulo
So DP[index][modulo] stores the modulus of the result of evaluation of the sequence formed till that index, with M.

```#include <bits/stdc++.h>
using namespace std;

const int MAX = 100;

int isPossible(int n, int index, int modulo,
int M, int arr[], int dp[][MAX])
{

// Calculate modulo for this call
modulo = ((modulo % M) + M) % M;

// Base case
if (index == n) {

// check if sum is divisible by M
if (modulo == 0)
return 1;
return 0;
}

// check if the current state is
if (dp[index][modulo] != -1)
return dp[index][modulo];

// 1.Try placing '+'
int placeAdd = isPossible(n, index + 1,
modulo + arr[index], M, arr, dp);

// 2. Try placing '-'
int placeMinus = isPossible(n, index + 1,
modulo - arr[index], M, arr, dp);

// calculate value of res for recursive
// case
bool res = (placeAdd || placeMinus);

// store the value for res for current
// states and return for parent call
dp[index][modulo] = res;
return res;
}

int main()
{
int arr[] = { 1, 2, 3, 4, 6 };
int n = sizeof(arr)/sizeof(arr[0]);
int M = 4;

// MAX is the Maximum value M can take
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;
}
```

The Complexity of this method is O(N*M).

If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.