during the contest i tried to check is there or not: such m numbers in array that sum of this numbers will be x.
i wrote code,but i dont know why it is not correct,so need your help:
int d[10001][101]={0};
d[0][0]=1;
for (i=1;i<=n;i++){
cin>>x;
for (j=10000;j>=0;j--)
for (k=0;k<n;k++)
if (d[j][k])
d[j+x][k+1]=1;
};
d[i][j]=1 if we can find in array j numbers where sum of this numbers will be i,otherwise d[i][j]=0;
P.S using this,i get WA6
UPDATE: i didn't know problem good. but this idea is correct,more formally problems same as above can solve in O(s*n*n) where s is the sum of numbers(all numbers positive).
Does your solution work for
3 1
15 16 17
14 22 17
got it