1244. Gentlemen Time limit: 0.5 second Memory limit: 64 MB Let's remember one old joke: Once a gentleman said to another gentleman: — What if we play cards? — You know, I haven't played cards for ten years… — And I haven't played for fifteen years… So, little by little, they decided to resurrect their youth. The first gentleman asked a servant to bring a pack of cards, and before starting playing out weighed in his hand the pack. — It seems to me, one card is missing from the pack… — he said and gave the pack to the other gentleman. — Yes, the nine of spades, — the man agreed. An incomplete pack of cards is given. The program should determine which cards are missing. Input The first line contains a positive integer, which is the weight in milligrams of the given incomplete pack. The second line contains an integer N, 2 ≤ N ≤ 100 — the number of cards in the complete pack. In the next N lines there are integers from 1 to 1000, which are the weights of the cards in milligrams. It's guaranteed that the total weight of all cards in the complete pack is strictly greater than the weight of the incomplete pack. Output If there is no solution, then output the single number 0. If there are more than one solutions, then you should write −1. Finally, if it is possible to determine unambiguously which cards are missing in the incomplete pack as compared to the complete one, then output the numbers of the missing cards separated with a space in ascending order. Samples input output 270 4 100 110 170 200 2 4 270 4 100 110 160 170 -1 270 4 100 120 160 180 0 Problem Author: Alexander Petrov Problem Source: Ural State University Personal Programming Contest, March 1, 2003 Tags: dynamic programming  ( hide tags for unsolved problems ) Seeing the constraints we can get some idea. First of all its a normal pick or leave dp with states being dp[pos][sum] . As position can go upto 100 and sum can go upto 1000*100 theferore we have the maximum size of the dp as  dp[100][100000].  Now we can wirte this normally sending a hash array in recursion to remember the positions used to create the weight.  We keep a global variable flag which shows the number of solutions. If it is one then there is single if 0 there is no solution else there are many solutions. Now we should stress on few facts. lets take the case of    12 12 6 1 4 3 1 2 5  In first recursion we visit position 4 with value 4 from the single 4 at arr[1] and we can also reach position 4 with val 1+3 from postion arr[1] +arr[3] . Hence we should check this condition too if(dp[pos][sum]!=-1) {        if(dp[pos][sum] ==1       flag++; return dp[pos][sum]; } if(dp[pos][sum]==1 ) takes care of the fact that if we are reaching here with same sum again and we can create a solution with the reached sum . Then the total number of solution increases by 1. Here is the code

#include<bits/stdc++.h>

using namespace std;

int n;

int tot;

int dp[110][100010];

int f=0;

int arr[110];

int ha[110];

int solve(int pos,int wt,int h[],int apos)

{

// cout<<"pos wt "<<pos<<" "<<wt<<endl;

if(pos==n)

{

if(wt==tot)

{

//               cout<<"answer "<<endl;

//               for(int i=0;i<apos;i++)

//               {

//               cout<<h[i]<<" ";

// }

//   cout<<endl;

f++;

if(f==1)

{

for(int i=0;i<apos;i++)

ha[h[i]]=1;

}

return 1;

}

return 0;

}

if(dp[pos][wt]!=-1)

{

if(dp[pos][wt]==1)

f++;

return dp[pos][wt];

}

int res=0;

h[apos]=pos;

res=solve(pos+1,wt+arr[pos],h,apos+1);

res|=solve(pos+1,wt,h,apos);

dp[pos][wt]=res;

return res;

}

int main()

{

cin>>tot;

cin>>n;

for(int i=0;i<n;i++)

{

cin>>arr[i];

}

int ar[110];

memset(dp,-1,sizeof(dp));

int res=solve(0,0,ar,0);

if(f==0)

cout<<"0"<<endl;

else if(f>1)

{

cout<<-1<<endl;

}

else

{

int bf=0;

for(int i=0;i<n;i++)

{

if(!ha[i])

{

bf++;

cout<<i+1<<" ";}

}

cout<<endl;

}

return 0;

}