> Suppose u r given a positive number N.
> How will we find a set of distinct positive numbers having sum equal
> to N.
> There could be multiple such sets so what is the algo to find all
> those sets.
Yes, this is the subset-sum problem but all is not lost.
There is a dynamic programming soluti
This is a Subset-Summation problem which is proven to be NP-Complete.
So there are no ways that you can devise a clever algo to solve it
accurately.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks"
The thing that you asked for is formally known as BFT (Breadth First
Traversal). Here's the pseudo-code that'll give you the idea in
general.
#define MAX 100
void BFT ( node *root )
{
node *p;
ins_Q(root);// inserting the node into a queue
do
{
My original concern with that logic for odd N is whether the +2 honest
majority would be maintained in the N-1 sample that we take to the
next round (since the odd man out might be honest). However, I see
now that this is of no concern, because if N is odd we will have a +3
majority (coming from
Google search for Integer Partitions.
On Apr 30, 9:04 am, Cool_Happy <[EMAIL PROTECTED]> wrote:
> Suppose u r given a positive number N.
> How will we find a set of distinct positive numbers having sum equal
> to N.
> There could be multiple such sets so what is the algo to find all
> those sets.
If I understand correctly this is subset-sum problem and is NP-
Complete.
On Apr 30, 9:04 am, Cool_Happy <[EMAIL PROTECTED]> wrote:
> Suppose u r given a positive number N.
> How will we find a set of distinct positive numbers having sum equal
> to N.
> There could be multiple such sets so what
OK, it's a long time for me too.
So let's see.
If we start with odd number of people, then we'll be left out with one
who won't be carried out in the next iteration.
Only when we found out at the end who the one truth teller is that we
ask the truth teller whether the left out single person is a l
