Dor,
Yes, you are right and your method works.
On Apr 3, 1:05 pm, "dor" <[EMAIL PROTECTED]> wrote:
> Yes, you do know S. The problem statements says find the *subset* of S
> that sums to k, if any.
> Not knowing S does not make any sense anyway. S and k are an instance
> of SUBSET-SUM.
>
> On A
Sorry for not understanding the problem at first...
I hope this solution will find the all the subsets from set S . The sum of
elements in subset is equivalent to certain k.
fun(int a[],int k){
int i,j;
int k1;
for(i=0;i<10;i++){
Yes, you do know S. The problem statements says find the *subset* of S
that sums to k, if any.
Not knowing S does not make any sense anyway. S and k are an instance
of SUBSET-SUM.
On Apr 2, 8:41 am, "pramod" <[EMAIL PROTECTED]> wrote:
> Dor,
>
> If I understand the problem correctly, we don't kno
Peeyush,
I believe u misunderstood the problem. The problem does not ask for
finding two numbers whose sum is K.
Read the problem statement again.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" gr
Following is the Solution for sum of subsets with complexity O(n).
suppose we have to find out the 2 numbers from array(Set) whose sum is
equivalent to certain no: k
int main(){
int a[10]={1,2,3,4,5,6,7,8,9,10};
int sum =15; //no. to find for
int i=0,j;
front=i;
back=10
while(fronta[front]+a[bac
Dor,
If I understand the problem correctly, we don't know what are all the
elements in S (that's what we need to find).
So how are you going to pick 'k' first and how do you know of 'x'
belonging to S?
--~--~-~--~~~---~--~~
You received this message because you a
Ok, so you have an oracle that gives you the answer for any SUBSET-SUM
(the decision problem) instance in O(n), and you want to use it to
actually construct the solution. It's obvious that you can construct
the solution in O(n^2) (at most n queries to the oracle).
Start with the initial set S. Que
OK. that is the assumption of the problem that this is done in O(n).
Perhaps it is imaginary.
The Question is :
assuming this algorithm and using that, now we want to find the exact
members that their sum equals to K, with the best order.
Thank you.
On Mar 30, 7:38 pm, "Muntasir Azam Khan" <[EMA
On Mar 30, 10:07 pm, "Muntasir Azam Khan" <[EMAIL PROTECTED]>
wrote:
> - Original Message -
> From: "Mahdi" <[EMAIL PROTECTED]>
> To: "Algorithm Geeks"
> Sent: Friday, March 30, 2007 1:27 PM
> Subject: [algogeeks] Sum of subsets
>
> > We have set named S. We assume we have an algorithm th
- Original Message -
From: "Mahdi" <[EMAIL PROTECTED]>
To: "Algorithm Geeks"
Sent: Friday, March 30, 2007 1:27 PM
Subject: [algogeeks] Sum of subsets
>
> We have set named S. We assume we have an algorithm that specifies if
> there is a subset in S that sum of it's elements equals to K
And we have to find all the elements of the set S using the sum method...
hence we don't have the members of the set S.
The method hence should more likely be like SUM(K) which returns TRUE or
FALSE if there's a subset, sum of whose elements is equal to k.
It is a very interesting problem...
On
No there's no assumptions...
How can it be sub string?
Say a set S = {1,4,12,62,11,3}
we are given an algo say SUM(S,k) which returns TRUE or FALSE if the set S
has a subset, sum of whose elsements is equal to K
SUM(S,5) = TRUE
SUM(S,74) =TRUE
SUM(S,&) = FALSE
On 3/30/07, Shalin Shah <[EMAIL PRO
> We have set named S. We assume we have an algorithm that specifies if
> there is a subset in S that sum of it's elements equals to K in O(n)
> and returns TRUE or FALSE.
That assumption is either wrong, or you have specified the problem
incorrectly. Is "subset" the right word? Do you mean "sub
13 matches
Mail list logo