<blockquote>
  <p><strong>Possible Duplicate:</strong><br>
  <a href="https://cstheory.stackexchange.com/questions/4644/faster-pseudo-polynomial-time-algorithms-for-partition">Faster pseudo-polynomial time algorithms for PARTITION</a>  </p>
</blockquote>



<p>I want to partition N given numbers( may or may not be equal) into 2 subsets such that the 2 subsets have sum as close as possible and also the cardinality of the sets are equal ( if n is even ) or differ only by 1 ( if n is odd)</p>

<p>I think we can do this in pseudo polynomial time O(n^2 * Sum of set)</p>

<p>Can I do better than this?</p>

<p>Thanks in advance!</p>

CC BY-SA 2.5
2011-01-30T13:17:30.140Z
Does `O(2^(n/2))` count as better?
IVlad
CC BY-SA 2.5
2011-01-30T13:20:53.620Z
@awoodland, This isn't a CSTheory level problem and @Firebrandt I think this is exactly 2-Partition problem, see wiki for details, or clarify your question with more details.
Saeed
CC BY-SA 2.5
2011-01-30T13:34:34.870Z
What is the best algorithm(pseudo polynomial) to solve this problem?
Firebrandt
CC BY-SA 2.5
2011-01-30T13:37:05.777Z
See wiki carefully, partition is a problem on "multiset" not set.
Saeed
CC BY-SA 2.5
2011-01-30T13:45:03.450Z
oh.. i dint see multiset..
Firebrandt
CC BY-SA 2.5
2011-01-30T14:17:54.023Z
I am looking for the optimisation version the partition problem ( as given in wiki) . the cardinality of the subsets must be equal(if even) or differ by one(if odd) and in addition the sum of the subsets must be as close as possible , i.e Minimise (Sum (subset1) - sum(subset2))
Firebrandt
CC BY-SA 2.5
2011-01-30T14:19:20.170Z
@ Saeed , I am deleting the previous wrong comment of mine..I am sorry about that i got confused...
Firebrandt
CC BY-SA 2.5
2011-01-30T14:35:57.330Z
@IVlad no 2^n/2 is not better...
Firebrandt
CC BY-SA 2.5
2011-02-02T11:33:13.720Z
The asker had (secretly) posted the same question both on cstheory.stackexchange.com and Stack Overflow, and the question on Stack Overflow was migrated here.  Seems like another reason why simultaneous crossposting and crossposting without linking are bad.  Voted to close as an exact duplicate.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-02T11:52:10.587Z
I have started a [meta discussion](http://meta.cstheory.stackexchange.com/q/919/186) about migration.
Kaveh
<ds.algorithms>
2 partition problem with equal cardinality
Firebrandt
# 2 partition problem with equal cardinality

(Asked by: username_0 on 2011-01-30)

> **Possible Duplicate:**  
> [Faster pseudo-polynomial time algorithms for PARTITION](https://cstheory.stackexchange.com/questions/4644/faster-pseudo-polynomial-time-algorithms-for-partition)

I want to partition N given numbers( may or may not be equal) into 2 subsets such that the 2 subsets have sum as close as possible and also the cardinality of the sets are equal ( if n is even ) or differ only by 1 ( if n is odd)

I think we can do this in pseudo polynomial time O(n^2 \* Sum of set)

Can I do better than this?

Thanks in advance!

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: Does `O(2^(n/2))` count as better?  
> **username_2**: @awoodland, This isn't a CSTheory level problem and @username_0 I think this is exactly 2-Partition problem, see wiki for details, or clarify your question with more details.  
> **username_0**: What is the best algorithm(pseudo polynomial) to solve this problem?  
> **username_2**: See wiki carefully, partition is a problem on "multiset" not set.  
> **username_0**: oh.. i dint see multiset..  
> **username_0**: I am looking for the optimisation version the partition problem ( as given in wiki) . the cardinality of the subsets must be equal(if even) or differ by one(if odd) and in addition the sum of the subsets must be as close as possible , i.e Minimise (Sum (subset1) - sum(subset2))  
> **username_0**: @ username_2 , I am deleting the previous wrong comment of mine..I am sorry about that i got confused...  
> **username_0**: @username_1 no 2^n/2 is not better...  
> **username_3**: The asker had (secretly) posted the same question both on cstheory.stackexchange.com and Stack Overflow, and the question on Stack Overflow was migrated here.  Seems like another reason why simultaneous crossposting and crossposting without linking are bad.  Voted to close as an exact duplicate.  
> **username_4**: I have started a [meta discussion](http://meta.cstheory.stackexchange.com/q/919/186) about migration.  

---

## 0 answers

