@ prem...
can U submit the code...for
all Subsets of the particular array with O(n^2).
thanks..
On Sun, May 20, 2012 at 1:11 AM, abhijeet srivastva <
nwaab.abhij...@gmail.com> wrote:
> This is a subset sum problem. You have to find a subset of elements of
> array whose sum is x/2, where x is
@abhijeet how could partitioning the array elements into two parts with
half the total sum each help, if the no. of elements in the two parts be
unequal resulting into unequal average?
On Sun, May 20, 2012 at 1:11 AM, abhijeet srivastva <
nwaab.abhij...@gmail.com> wrote:
> This is a subset sum p
This is a subset sum problem. You have to find a subset of elements of
array whose sum is x/2, where x is sum of all the elements of the array.
On Sat, May 19, 2012 at 2:07 PM, payal gupta wrote:
> this wont work out as we need to partition the elements to get the average
> of the two parts to b
this wont work out as we need to partition the elements to get the average
of the two parts to be equal and not the sum of the two parts..
On Fri, May 18, 2012 at 11:57 PM, Ramindar Singh wrote:
> Not sure if i am correct but still be very close.
>
> 1. Intial Array is A with n elements
> 2. Sor
Not sure if i am correct but still be very close.
1. Intial Array is A with n elements
2. Sort the Array's in descending order
3. take 2 more arrays B and C in which u keep the partition
4. pull the one element from A to B and keep keep track of the sum's in
both the arrays B & C
5. Try to reach
ignore my last post ...
Thnx for the suggestions..
On Sat, May 19, 2012 at 10:29 AM, payal gupta wrote:
> @adarsh why have we taken an assumption of the average to be integer all
> the time it could be float as well?
> @prem how could we find all possible subsets in tc-O(n2) as it will
> clearl
@adarsh why have we taken an assumption of the average to be integer all
the time it could be float as well?
@prem how could we find all possible subsets in tc-O(n2) as it will clearly
be exponential...
On Sat, May 19, 2012 at 8:58 AM, Gene wrote:
> We discussed this some time ago. It's NP har
We discussed this some time ago. It's NP hard. So an algorithm that
gets the correct answer every time will run in exponential time. You
can do it in pseudo-polynomial time -- polynomial in the magnitude of
the elements - by using the DP method used for subset sum.
On May 18, 2:35 am, payal gup