<p>One can solve the decision problem in $\tilde{O}(nA)$ time.</p>

<p>Let the sequence of numbers be $S$. Define $F_S$ to be a set such that $(i,j)\in F_S$ iff there exist a subsequence of $S$ of length $j$ that sums to $i$. If we have computed $F_S$, then we just need $O(nA)$ additional time to go thorough $F_S$ to solve your problem.</p>

<p>If $S_1$ and $S_2$ are two subsequences that partitions $S$, then </p>

<p>$$F_S = F_{S_1} + F_{S_2}$$</p>

<p>where $A+B=\{a+b  | a\in A, b\in B\}$ is the minkowski sum, and addition between tuples are defined coordinate-wise. </p>

<p>Claim: Computing $F_S$ from $F_{S_1}$ and $F_{S_2}$ takes $\tilde{O}(|S|A)$ time.</p>

<p>Proof: Apply 2D convolution on two tables of size $A\times |S|$. </p>

<p>The algorithm partition the sequence to two equal sized sequences, apply recursion to each, and take the minkowski sum of the result. Let $T_A(n)$ be the worst case running time when the input to the algorithm has $n$ elements and $A$ is an upper bound of the sum.
We have<br>
$$
T_A(n) = 2 T_A(n/2) + A \tilde{O}(n)
$$
Which shows $T_A(n) = \tilde{O}(n A)$.</p>

<p>The hidden $\log$ factor is $\log n \log nA$.</p>

CC BY-SA 3.0
2015-07-08T19:57:17.213Z
2015-07-08T19:57:17.213Z
Chao Xu
<p>If anybody care about the $\log$ factors, with careful analysis we can prove the time complexity for Chao's algorithm is $O(nA\log(nA))$.</p>

<p>Proof. At the even-th layer of the recursion tree, we partition the set $S$ into two equally sized set $S_1$ and $S_2$, which gives
$$T_e(n,A)=T_o(n/2,A')+T_o(n/2,A-A')+O(nA\log(nA)),$$
and at the odd-th layer of the recursion tree, we partition the set $S$ into two "equally sumed" set $S_1$ and $S_2$. To be precise, we can partition a set $S$ with sum $A$ into two sets $S_1$ and $S_2$ with each of them sum up to $\leq A/2$, with at most one element left. We can deal with that element with trivial dynamic programming in $O(A)$. This gives
$$T_o(n,A)=T_e(n_1,A/2)+T_e(n-n_1,A/2)+O(nA\log(nA)),$$
where $n_1=|S_1|$. Therefore we have
$$T(n,A)\leq \sum_{i=1}^4T(n_i,A_i)+O(nA\log(nA)),$$
where $\sum_{i=1}^4n_i\leq n$, $\sum_{i=1}^4A_i\leq A$, and $\forall i,~n_i\leq n/2,~A_i\leq A/2$. This will give us $T(n,A)=O(nA\log(nA))$.</p>

CC BY-SA 4.0
2018-09-11T22:23:23.573Z
2018-09-11T22:23:23.573Z
hqztrue
<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 A)$, where $A$ is the sum of numbers in the set.</p>

<p>Can I do better than this? Namely, is there a pseudo polynomial time algorithm that runs in time $O(n^c A)$ with $c &lt; 2$?</p>

<p>Thanks in advance!</p>

CC BY-SA 2.5
2011-01-30T14:10:23.330Z
Notice that as a special case of Knapsack, it has an [FPTAS](http://en.wikipedia.org/wiki/FPTAS). See e.g. [E.L.Lawler. Fast approximation algorithms for knapsack problems](http://dx.doi.org/10.1109/SFCS.1977.11).
Mathieu Chapelle
CC BY-SA 2.5
2011-01-30T16:06:54.227Z
@Oleksandr, THanks for that. Could you also please tell me how to solve it in O(nA) , the book just says it can be solved so.
Firebrandt
CC BY-SA 2.5
2011-01-30T16:07:39.083Z
@Firebrandt: Please, specify your question: what do you mean by "better"?
Oleksandr Bondarenko
CC BY-SA 2.5
2011-01-30T16:14:28.073Z
@Firebrandt: Book says that it can be solved "in time bounded by low order polynomial in the number of table entries", and this doesn't imply $\mathcal{O}(nA)$. Thus it's possible that you can't do better.
Oleksandr Bondarenko
CC BY-SA 2.5
2011-01-30T16:38:13.823Z
@Oleksandr , by better I meant is there a pseudo polynomial algorithm which runs in O(nA).
sorry that i am unable to post in latex.
Firebrandt
CC BY-SA 2.5
2011-01-30T16:41:29.623Z
If so , could you please outline the solution?
thanks!
Firebrandt
CC BY-SA 2.5
2011-01-30T16:47:10.627Z
@Firebrandt: Could you, please, add the clarification what you meant by better in your question. What do you mean by outlining the solution - how to fill table entries in the table from Garey and Johnson book?
Oleksandr Bondarenko
CC BY-SA 2.5
2011-01-30T16:47:38.247Z
Firebrandt, could you please explain the motivation behind this question, i.e. why are you interested in this question?
Kaveh
CC BY-SA 2.5
2011-01-30T17:01:11.137Z
I am searching for solutions to the optimisation version of the 2-Partition problem http://en.wikipedia.org/wiki/Partition_problem (as given in wiki) - "Find a partition into two subsets S1,S2 such that \max(\operatorname{sum}(S_1), \operatorname{sum}(S_2)) is minimized (sometimes with the additional constraint that the sizes of the two sets in the partition must be equal, or differ by at most 1 )".

This problem differs from the standard partition problem in that, the cardinality of the subsets must be equal(even) , or differ by 1(odd)
Firebrandt
CC BY-SA 2.5
2011-01-30T20:55:37.360Z
I am afraid that this question is on the border of being too elementary.  For example, “Is the Partition problem with the additional restriction that the two sets must have equal cardinality still NP-complete?” can be a typical homework question and I am afraid that writing down the answer may have negative impact on some courses in computational complexity.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-30T21:17:51.207Z
@Tsuyoshi: Should it be closed if it's "on the border of being too elementary"?
Oleksandr Bondarenko
CC BY-SA 2.5
2011-01-30T21:22:26.327Z
@Oleksandr: I do not have an answer, in general or for this specific question.  I am thinking about voting to close this question.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-31T04:01:30.593Z
Firebrandt, could you please explain why you are searching for a solution to "the 2-Partition problem"? e.g. are you working on some other research problem which is related to this question? Note that this site is for *research level* questions, so if the question is not research level and there is not a good research related motivation for it then it is probably not appropriate for cstheory and may get closed as off-topic. (you may want to try [Math.SE](http://math.stackexchange.com).)
Kaveh
CC BY-SA 2.5
2011-01-31T19:27:54.457Z
How is this too elementary? The obvious approach gives $O(n^2A)$, and the question is whether there's a better algorithm running in time $O(n^c A)$ where $c < 2$. My guess is that this is an open question.
Peter Shor 
CC BY-SA 2.5
2011-02-01T20:44:26.067Z
@Peter: I interpreted this question as asking whether the Partition problem with the additional restriction is solvable in polynomial time.  That question can be an exercise in a course of computational complexity theory.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-01T20:49:53.147Z
@Tsuyoshi: it was clarified in the comments: "is there a pseudopolynomial time algorithm that runs in time $O(nA)$." (I agree it should have been clarified by editing the original post.)
Peter Shor 
CC BY-SA 2.5
2011-02-01T20:54:24.323Z
@Peter: I confess that I did not read all the comments.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-01T20:56:18.727Z
@Firebrandt: I took the liberty of editing your original question to add my version of your clarification (changing $O(nA)$ to $O(n^cA)$ with $c<2$, since I think even that's probably an open question). Feel free to change it back to $O(nA)$ if you want. I think the question, as clarified by your comments, is clearly research-level.
Peter Shor 
CC BY-SA 2.5
2011-02-01T21:13:26.263Z
I suggest renaming question to "Partition problem with equal cardinality", since Partition and 2-Partition are different problems and the latter one is in P.
Oleksandr Bondarenko
CC BY-SA 2.5
2011-02-01T21:23:48.980Z
I do not think that “with equal cardinality” is an essential part of the question.  Therefore my suggestion is along “Faster pseudo-polynomial-time algorithm for the Partition problem.”
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-01T23:38:56.730Z
I agree ... the constraints on equal cardinality very likely will not change the complexity.
Peter Shor 
CC BY-SA 2.5
2011-02-02T00:29:03.580Z
since there's agreement, I just changed the title.
Suresh Venkat
CC BY-SA 2.5
2011-02-02T12:42:11.013Z
I'm a bit confused.  There's an $O(nA)$-time algorithm for the knapsack problem and the partition problem (for example, see http://en.wikipedia.org/wiki/Knapsack_problem, and I've checked several textbooks, where this classical fact is presented).  An easy adaptation should give an $O(nA)$-time algorithm for the proposed problem too.  I don't see what I'm missing.
Yoshio Okamoto
CC BY-SA 2.5
2011-02-02T15:46:26.227Z
@Yoshio Okamoto, this is not partition problem and I think it's strong NP problem and there is no pseudo polynomial algorithm with this, restriction of length of sets makes it difficault, I don't know how to reduce it, but it's not as simple as links you left. and @Firebrandt, how do you want solve it in O(n^2 A)? left it as answer, if it's true, I'll upvote it.
Saeed
CC BY-SA 2.5
2011-02-02T16:12:02.797Z
@Saeed: I was thinking of the problem without equal-cardinality constraint. So, my "easy adaptation" doesn't work, and I was wrong.  However, $O(n^2 A)$ is possible, by creating a 3-dimensional table $m[i,j,W]$ that represents the existence of a set in $\{1,...,i\}$ of cardinality $j$ with weight $W$.
Yoshio Okamoto
<ds.algorithms><co.combinatorics><partition-problem>
Faster pseudo-polynomial time algorithms for PARTITION
Firebrandt
# Faster pseudo-polynomial time algorithms for PARTITION

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

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 A)$, where $A$ is the sum of numbers in the set.

Can I do better than this? Namely, is there a pseudo polynomial time algorithm that runs in time $O(n^c A)$ with $c < 2$?

Thanks in advance!

**Tags:** ds.algorithms, co.combinatorics, partition-problem

> **Comments:**
> **username_1**: Notice that as a special case of Knapsack, it has an [FPTAS](http://en.wikipedia.org/wiki/FPTAS). See e.g. [E.L.Lawler. Fast approximation algorithms for knapsack problems](http://dx.doi.org/10.1109/SFCS.1977.11).  
> **username_0**: @Oleksandr, THanks for that. Could you also please tell me how to solve it in O(nA) , the book just says it can be solved so.  
> **username_2**: @username_0: Please, specify your question: what do you mean by "better"?  
> **username_2**: @username_0: Book says that it can be solved "in time bounded by low order polynomial in the number of table entries", and this doesn't imply $\mathcal{O}(nA)$. Thus it's possible that you can't do better.  
> **username_0**: @Oleksandr , by better I meant is there a pseudo polynomial algorithm which runs in O(nA). sorry that i am unable to post in latex.  
> **username_0**: If so , could you please outline the solution? thanks!  
> **username_2**: @username_0: Could you, please, add the clarification what you meant by better in your question. What do you mean by outlining the solution - how to fill table entries in the table from Garey and Johnson book?  
> **username_3**: username_0, could you please explain the motivation behind this question, i.e. why are you interested in this question?  
> **username_0**: I am searching for solutions to the optimisation version of the 2-Partition problem http://en.wikipedia.org/wiki/Partition_problem (as given in wiki) - "Find a partition into two subsets S1,S2 such that \max(\operatorname{sum}(S_1), \operatorname{sum}(S_2)) is minimized (sometimes with the additional constraint that the sizes of the two sets in the partition must be equal, or differ by at most 1 )".  This problem differs from the standard partition problem in that, the cardinality of the subsets must be equal(even) , or differ by 1(odd)  
> **username_4**: I am afraid that this question is on the border of being too elementary.  For example, “Is the Partition problem with the additional restriction that the two sets must have equal cardinality still NP-complete?” can be a typical homework question and I am afraid that writing down the answer may have negative impact on some courses in computational complexity.  
> **username_2**: @Tsuyoshi: Should it be closed if it's "on the border of being too elementary"?  
> **username_4**: @Oleksandr: I do not have an answer, in general or for this specific question.  I am thinking about voting to close this question.  
> **username_3**: username_0, could you please explain why you are searching for a solution to "the 2-Partition problem"? e.g. are you working on some other research problem which is related to this question? Note that this site is for *research level* questions, so if the question is not research level and there is not a good research related motivation for it then it is probably not appropriate for cstheory and may get closed as off-topic. (you may want to try [Math.SE](http://math.stackexchange.com).)  
> **username_5**: How is this too elementary? The obvious approach gives $O(n^2A)$, and the question is whether there's a better algorithm running in time $O(n^c A)$ where $c < 2$. My guess is that this is an open question.  
> **username_4**: @Peter: I interpreted this question as asking whether the Partition problem with the additional restriction is solvable in polynomial time.  That question can be an exercise in a course of computational complexity theory.  
> **username_5**: @Tsuyoshi: it was clarified in the comments: "is there a pseudopolynomial time algorithm that runs in time $O(nA)$." (I agree it should have been clarified by editing the original post.)  
> **username_4**: @Peter: I confess that I did not read all the comments.  
> **username_5**: @username_0: I took the liberty of editing your original question to add my version of your clarification (changing $O(nA)$ to $O(n^cA)$ with $c<2$, since I think even that's probably an open question). Feel free to change it back to $O(nA)$ if you want. I think the question, as clarified by your comments, is clearly research-level.  
> **username_2**: I suggest renaming question to "Partition problem with equal cardinality", since Partition and 2-Partition are different problems and the latter one is in P.  
> **username_4**: I do not think that “with equal cardinality” is an essential part of the question.  Therefore my suggestion is along “Faster pseudo-polynomial-time algorithm for the Partition problem.”  
> **username_5**: I agree ... the constraints on equal cardinality very likely will not change the complexity.  
> **username_6**: since there's agreement, I just changed the title.  
> **username_7**: I'm a bit confused.  There's an $O(nA)$-time algorithm for the knapsack problem and the partition problem (for example, see http://en.wikipedia.org/wiki/Knapsack_problem, and I've checked several textbooks, where this classical fact is presented).  An easy adaptation should give an $O(nA)$-time algorithm for the proposed problem too.  I don't see what I'm missing.  
> **username_8**: @username_7, this is not partition problem and I think it's strong NP problem and there is no pseudo polynomial algorithm with this, restriction of length of sets makes it difficault, I don't know how to reduce it, but it's not as simple as links you left. and @username_0, how do you want solve it in O(n^2 A)? left it as answer, if it's true, I'll upvote it.  
> **username_7**: @username_8: I was thinking of the problem without equal-cardinality constraint. So, my "easy adaptation" doesn't work, and I was wrong.  However, $O(n^2 A)$ is possible, by creating a 3-dimensional table $m[i,j,W]$ that represents the existence of a set in $\{1,...,i\}$ of cardinality $j$ with weight $W$.  

---

## 2 answers

### Answer by username_9 on 2015-07-08. Score: 7

One can solve the decision problem in $\tilde{O}(nA)$ time.

Let the sequence of numbers be $S$. Define $F\_S$ to be a set such that $(i,j)\in F\_S$ iff there exist a subsequence of $S$ of length $j$ that sums to $i$. If we have computed $F\_S$, then we just need $O(nA)$ additional time to go thorough $F\_S$ to solve your problem.

If $S\_1$ and $S\_2$ are two subsequences that partitions $S$, then

$$F\_S = F\_{S\_1} + F\_{S\_2}$$

where $A+B=\{a+b | a\in A, b\in B\}$ is the minkowski sum, and addition between tuples are defined coordinate-wise.

Claim: Computing $F\_S$ from $F\_{S\_1}$ and $F\_{S\_2}$ takes $\tilde{O}(|S|A)$ time.

Proof: Apply 2D convolution on two tables of size $A\times |S|$.

The algorithm partition the sequence to two equal sized sequences, apply recursion to each, and take the minkowski sum of the result. Let $T\_A(n)$ be the worst case running time when the input to the algorithm has $n$ elements and $A$ is an upper bound of the sum.
We have  
$$
T\_A(n) = 2 T\_A(n/2) + A \tilde{O}(n)
$$
Which shows $T\_A(n) = \tilde{O}(n A)$.

The hidden $\log$ factor is $\log n \log nA$.


---

### Answer by username_10 on 2018-09-11. Score: 3

If anybody care about the $\log$ factors, with careful analysis we can prove the time complexity for Chao's algorithm is $O(nA\log(nA))$.

Proof. At the even-th layer of the recursion tree, we partition the set $S$ into two equally sized set $S\_1$ and $S\_2$, which gives
$$T\_e(n,A)=T\_o(n/2,A')+T\_o(n/2,A-A')+O(nA\log(nA)),$$
and at the odd-th layer of the recursion tree, we partition the set $S$ into two "equally sumed" set $S\_1$ and $S\_2$. To be precise, we can partition a set $S$ with sum $A$ into two sets $S\_1$ and $S\_2$ with each of them sum up to $\leq A/2$, with at most one element left. We can deal with that element with trivial dynamic programming in $O(A)$. This gives
$$T\_o(n,A)=T\_e(n\_1,A/2)+T\_e(n-n\_1,A/2)+O(nA\log(nA)),$$
where $n\_1=|S\_1|$. Therefore we have
$$T(n,A)\leq \sum\_{i=1}^4T(n\_i,A\_i)+O(nA\log(nA)),$$
where $\sum\_{i=1}^4n\_i\leq n$, $\sum\_{i=1}^4A\_i\leq A$, and $\forall i,~n\_i\leq n/2,~A\_i\leq A/2$. This will give us $T(n,A)=O(nA\log(nA))$.


---

