# Going deeper with pseudo-polynomial time algorithm for set partitioning

If I have a set of (edit) positive integers, and I'm sure that the pseudo-polynomial time algorithm for partitioning the problem will not give me an answer - what would I do next?

To illustrate this problem let's take a look at this example: {100,1,2,3}.

The p-p algorithm will give an answer False, and then I can end with result: This set can be partitioned into two set with difference 100-6 = 94

(The 6 is the last result from p-p algorithm on with [_][vector.size()] = True, the 106 is the sum of all digits).

But what if I really would like to know the maximum by sum two-split of this set in which every subset has the same sum - for example the result that I'm looking for should be 3. This set - {100,1,2,3} can be split (by bypassing the 100) into two subset with the same sum - {1,2} and {3}.

How can I achieve this result?

• Why "106-6" - where does 106 come from? Should it be "100-6=94"? – Erel Segal-Halevi Jan 5 at 17:43
• You are right. Edited after 5 years (; – kowal66b Jan 7 at 11:33

## 1 Answer

You can extend the dynamic programming algorithm to handle this variant. Suppose that the weights are $w_1,\ldots,w_n$. You are looking for a vector $x \in \{0,\pm 1\}^n$ such that $\sum_{i=1}^n x_i w_i = 0$, and $\sum_{i=1}^n |x_i| w_i$ is as large as possible. This suggests two possible approaches. The first approach is to construct a large table keeping track of all possible pairs of values $(\sum_{i=1}^m x_i w_i, \sum_{i=1}^m |x_i| w_i)$, where $x_1,\ldots,x_m \in \{0,\pm 1\}^m$. This leads to an $O(nM^2)$ algorithm, compared to the $O(nM)$ subset-sum or partition algorithms.

The second approach is to explicitly list all vectors $x$ such that $\sum_{i=1}^n x_i w_i = 0$ (using dynamic programming), and choose the one maximizing $\sum_{i=1}^n |x_i| w_i$. This takes time $O(nM + nS)$, where $S$ is the number of vectors $x$ such that $\sum_{i=1}^n x_i w_i = 0$. In practice $S$ might be small enough for this approach to be practical.

• It should be more simple if I know that all of the numers are positive integers and the sum S is less then 10^6. – kowal66b Mar 27 '15 at 11:06
• could you please help with this second approach and write down the simple pseudo code with I can fallow. Thank you. – kowal66b Mar 27 '15 at 12:32
• No, writing pseudocode is your job. – Yuval Filmus Mar 27 '15 at 13:34
• Ok, but I'm just wondering about the proccess of filling the table. Should I fill it with minimal value of previous states (set with less numbers) + {-1,0,1}*(next w_i) and after that backtracking the result that have sum of all = 0? – kowal66b Mar 27 '15 at 13:47
• You should keep track of all possible values of $\sum_{i=1}^m x_i w_i$ at any given point. Whenever you find that $0$ is possible, you go back and construct the corresponding $x$s. That's the basic idea. – Yuval Filmus Mar 27 '15 at 13:49