OJ Board

if I have n numbers. a1, a2, a3, ... an
and I want to know if I can form some number with sum of anothers numbers..how to do it for big inputs in a fast way??

for example, if I have : 2 4 1 8
there is no way I can form one of this numbers by using the others numbers, ( I just can sum the other numbers)
but if I have : 1 2 3 5 9
I can form 9 by doing 1 + 3 + 5
or I can form 3 by doing 2 + 1
or I can form 5 by doing 2 + 3
etc....
I just care if I can form one number (it's not important which number) using the others numbers ...
I hope to be clear ....sorry but I am not good with english..
please, if it's not clear the problem let me know and I would try to explain it better!
thanks!
byeeee

As long as you know the bound (MAX) you can do it in O(n^2) by keeping a table.
int bigarr[MAX];
bigarr[0]=1; /* rest all 0 */
int arr[]={1,3,4,5,9};

for(i=0;i<sizeof(arr);i++)
{
for(j=MAX-1;j>=1;j--)
if(bigarr[j]==1)
{

bigarr[j+arr]++;
}
}

for(j=0;j<sizeof(arr[];j++)
if(bigarr[arr[j]]!=1)
some of the array elements add to this number

if j==sizeof(arr[])
no elements add to each other.

Otherwise if you don't know the bounds you will have to use the sum of subsets. It is O(2^n).
hope this is clear.

thanks a lot!!! your code help me a lot!
but...I still don't understand what is the idea behind that????
I mean the why...

thanks again!
byee

its idea is:
when you can make some number j from arr[0]~arr[i-1], you can make the number j+arr from arr[0]~arr by add the number arr into the number chosen above to make j.
So we use an array to record if we can make some particular number, using sets of number arr[0]; arr[0]~arr[1]; arr[0]~arr[2]; ... arr[0]~arr[n-1], each once. And since we can compute the result of arr[0]~arr[i-1],
and you can build new answer to problem for arr[0]~arr from the answer to problem for arr[0]~arr[i-1], we can use only one array.
After the computation above, we simply check all input number to see if we had recorded some number in the input has been marked (which is mean it can be make from other number).

thanks a lot!!!!
but...in the algorithm of nixtr....
shouldn't be "for(j=MAX-1;j>=0;j--) " instead of "for(j=MAX-1;j>=1;j--) "

and

"if(bigarr[arr[j]]>1)
some of the array elements add to this number "

instead of

"if(bigarr[arr[j]]!=1)
some of the array elements add to this number "...because if bigarr==0 then no elements sum to this number

right???'


thanks again!!!

I find one mistake in this algorithm. Algorithm should be
if(bigarr[j]>=1) {
bigarr[j+arr]++;
}
instead of
if(bigarr[j]==1) {
bigarr[j+arr]++;
}
New version of program for this task following:
int i,j;
int bigarr[MAX];
int arr[]={1,3,4,5,9};

for(i=0; i<MAX; i++) bigarr=0;
bigarr[0]=1;

for(i=0; i<sizeof(arr)/sizeof(int); i++)
for(int j=MAX-1; j>=0; j--)
if(bigarr[j]>=1) bigarr[j+arr]++;
for(i=0; i<sizeof(arr)/sizeof(int); i++)
if(bigarr[arr]>1)
This number can be presented as sum of another numbers.

you are right!
thanks