CODEWITHSUNDEEP
c++algorithm
James Rodrigues
James Rodrigues

Reputation: 107

Partition of set {1, 2, 3, ... N}

Given the subset {1, 2, 3, .... N}. I have to find the number of ways a set of all integers from 1 to N can be partitioned into two subsets with equal sums.

Nothing comes to my head. I want to try "Brute-force search", but it can make time limit. Is there any fast algorithms?

Upvotes: 1

Views: 1113

Answers (4)

W.F.
W.F.

Reputation: 13988

I think the problem is NP-hard so I don't think you can find an optimal solution in polynomial time (unless P=NP).

Edit: Yes, as my successors pointed out I was talking about more general problem of set bipartition and there should be a simple way to find out every possible set pairs.

Upvotes: 1

Tyler Durden
Tyler Durden

Reputation: 11572

To break the problem down...

Imagine you want to find the subsets of only 2 numbers that sum to a value. Obviously you can do this in linear time. For example, if the set is { 1, 2, 4, 7, 9 } and the value is 11, then starting from one end (1) you go backwards from the other and reach 9 (no match). So, now you increment the bottom number index by one (=2), it matches 9. Increment again (=4). and so on. Doing this you only need to make ONE pass through the list of values.

Of course this only solves the 2-member subset part of the problem.

So, now repeat the procedure for the 3-member subset. You can use exactly the same technique, except using 3 cursors instead of 2. And so on...

I do not know the complexity as a function of the number of cursors, it is probably log N, but in any case it will be way way faster than brute force search. If it is log N, then the total complexity would N log N, where N is the number of elements in the set.

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65516

It's computable in polynomial time as the coefficient of x^(n(n+1)/4) in the product of (1 + x^k) for k from 1 to n. There are several ways to evaluate the product; multiplying the terms one by one should suffice.

Upvotes: 5

RyanP
RyanP

Reputation: 1918

I don't know if there is purely a mathematical way to solve this, or something super fancy... but my first intuition would be that since you know the numbers are contiguous, at any point in the list you should be able to tell what the sum up to that point is. Therefore you should be able to make some smart selections if you choose to brute-force it on lots of permutations that should not be possible, to eliminate a lot of the cases you need to check.

Upvotes: 0

Related Questions