#### CONCEPTS USED:

Dynamic programming.

#### DIFFICULTY LEVEL:

Hard

#### PROBLEM STATEMENT`(`

SIMPLIFIED`)`

:

Arnab is now given N numbers, which are actually stacks of coins containing

`a[i]`

amount of coins each. Now he is asked to choose any subset of the stacks of coins. But there is a problem Arnab has two brothers and he has to divide the coins equally into three divisions. Find the largest sum of coins which satisfies the above conditions.

#### For Example :

```
1
3
1 4 2
The set {2,4} is the only possible maximum set,
so there are 6 coins which can be divided into three equal groups.
```

#### SOLVING APPROACH:

**You are advised to do Maximum Subset Sum using Recursion (if you haven’t) first and then come to this problem .**

- You have to find subsets for an array , whose sum is divisible by 3.
- As there can be many such subsets , print one with maximum sum.

#### You are encouraged to implement the above brute force and think of memoization on your own first ,before looking at the solution.

**See original problem statement here**

**BRUTE FORCE:**

Let’s define a function

`f(i,sum)`

where i is the current index and sum ranges from 0 to 2, which is the remainder obtained by dividing it with 3.For every index i ,

`a[i]`

will either be included in the sum or not included.If it is not included,then

increase the index and recur further.If included, then

`f(i,sum)`

will be the maximum of`a[i]`

not included and`a[i]`

+`solve(i+1,(sum+a[i])%3,v)`

.Brute force approach will take exponential time to calculate the required sum.But if we use recursion with memoization ,we can optimize it using the fundamentals of data structures in c++.

Before proceeding to the solution we can see that the recursive solution will thake exponential time

`(`

without memoization`)`

so we will proceed to thedynamic programmingapproach.

## Refer to the code for implementation.

[TABS_R id=2164]

[forminator_quiz id=”2165″]

**Space complexity- O(N*N).**