# CHECANDY-Editorial

PRACTICE
Editorialist: Yogesh Yogendra

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:

1. 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:

5
5 3 14 2 4

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;
}

You could have kept 1 \leq N, S \leq 10^5, S is the total number of candies.

1 Like