# PROBLEM LINK:

PRACTICE

*Editorialist:* Yogesh Yogendra

# DIFFICULTY:

HARD

# PREREQUISITES:

Dynamic Programming

# PROBLEM:

Chef wanted to impress chefina so he took her to a candy shop.

Chef asked Shopkeeper to bring N Boxes of Candies. Each Box contain some number of candies.

Chef wanted to distribute the candies between chef & chefina, but their is one condition:

- All candies of each box can be given to either chef or chefina i.e

For example:

if their are 5 Boxes and each box contain some number of candies. Box = [5,3,14,2,4] then

All candies of 1st box can be given to either chef or chefina

All candies of 2nd box can be given to either chef or chefina and so onâ€¦

If total candies can be equally distributed between Chef and Chefina, then Chefina will be impressed by chef otherwise no.

You have to find if Chef can impress Chefina or not.

## Input:

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains a single integer N i.e total number of boxes

The Second line of each test case contains N space seperated integers i.e Total number of candies of each boxes.

## Output:

Print â€śImpressedâ€ť without quotes if Chef is able to impress Chefina, otherwise print â€śNot Impressedâ€ť without quotes.

## Constraints:

1 <= T <= 10

1 <= N <= 100

1 <= Total number of candies of each boxes <= 1000

## Sample Testcase:

### Input:

5

5 3 14 2 4

### Output:

Impressed

### Explanation:

Chef will take [5,3,2,4]

Chefina will take [14]

Impressed Because Candies are equally distributed.

# EXPLANATION:

This question was basically the Partition Equal Subset Sum Problem.I have expained this question in a video, Link = https://youtu.be/s4fsOuWOVOg , go and have a look.

# SOLUTION:

```
#include<bits/stdc++.h>
#define int long long int
using namespace std;
int dp[1001][1001];
int solve(int n,int a[],int s){
if(n == -1){
if(s == 0)
return 1;
return 0;
}
if(s<0)
return 0;
if(s==0)
return 1;
if(dp[n][s]!=-1) return dp[n][s];
return dp[n][s] = solve(n-1,a,s-a[n]) || solve(n-1,a,s);
}
int equalPartition(int N, int arr[])
{
int s = 0;
for(int i=0;i<N;i++) s += arr[i];
if(s&1) return 0;
s=s/2;
dp[N][s];
memset(dp,-1,sizeof(dp));
return solve(N-1,arr,s);
}
int32_t main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++) cin>>a[i];
if(equalPartition(n,a)) cout<<"Impressed\n";
else cout<<"Not Impressed\n";
}
return 0;
}
```