Subset-sum: Given a list of numbers, find if a non-empty sublist has sum 0 (there's a variation where we want sum=k instead of 0, but 0 is easier for analysis)

Partition: Given a list, can it be partitioned into two non-empty sublists with equal sum?

I want to reduce subset-sum to partition. The reductions I found so far are same as this one but it has following faults :

  1. For $B=0$, you can always partition $L'$ into $\{2S-0\}$, $\{S+0\} U L$.
  2. It supposes $2S-B$ and $S+B$ have to go to different partitions! You could have both of them in same partition along with elements that sum to $-S$, hence total sum $= 2S$ as needed.
  • 2
    $\begingroup$ Shouldn't this be a comment on the answer you link to? $\endgroup$
    – Raphael
    Commented Nov 24, 2012 at 20:16
  • $\begingroup$ didn't want to dig up an old grave, and didn't think i would get replies over there ... $\endgroup$
    – Karan
    Commented Nov 24, 2012 at 20:19
  • $\begingroup$ Users get notified when somebody comments on their posts, and Yuval is an active user. But never mind, you don't have the rep to comment, anyway. I think this is a fair question to post, and I suspect Yuval will give you an answer. $\endgroup$
    – Raphael
    Commented Nov 24, 2012 at 20:20

1 Answer 1

  1. You're absolutely right that this partition always occurs. If you consider what this means in terms of the corresponding subset, you'll find that this indicates that the empty set (which is always a subset) has sum 0. In fact, this indicates the there is always a solution to subset sum when the target is 0, which is exactly as expected. It turns out fixing the target sum to 0 does not just make the problem easier to discuss, it makes it easier in a complexity sense ($O(1)$ by outputting YES immediately).

  2. You're right here too. There is a formulation of subset sum where the input is a list of positive integers, and I think the reduction you are reading was from that language. The goal was to have our added elements be large enough that they cannot both go in the same part. To patch that up, we can use the sum of the absolute values. This actually shows some of the structure of the proof better, because $2S$ was actually $S +$ some-large-enough-number-for-which-$S$-will-suffice-but-so-do-larger-numbers.

At this point I'm copy-pasting from the linked post and just editing to handle negatives:

Let $(L,B)$ be an instance of subset sum, where $L$ is a list (multiset) of numbers, and $B$ is the target sum. Let $S = \sum L$ and choose $S' > \sum_{l \in L} |l|$. Let $L'$ be the list formed by adding $S'+B,S'+S-B$ to $L$.

(1) If there is a sublist $M \subseteq L$ summing to $B$, then $L'$ can be partitioned into two equal parts: $M \cup \{ S' + S-B \}$ and $L\setminus M \cup \{ S'+B \}$. Indeed, the first part sums to $B+(S'+S-B) = S'+S$, and the second to $(S-B)+(S'+B) = S'+S$.

(2) If $L'$ can be partitioned into two equal parts $P_1,P_2$, then there is a sublist of $L$ summing to $B$. The sum of the two new elements is $(S'+B)+(S'+S-B) = 2S'+S$. All subsets $A \subset L$ have $\left|\sum A\right| < S'$, so it is not possible that $\{S'+S-B\} \cup \{ S'+B \} \cup A$ has sum $S' + S$ (it is always greater). So the two new elements belong to different parts. Without loss of generality, $S'+S-B \in P_1$. The rest of the elements in $P_1$ belong to $L$ and sum to $B$; they do not include a new element, so they are a solution to subset sum.

  • $\begingroup$ I was thinking in term of subset sum as defined on wikipedia where 0 sum is required of a non-empty subset, but not sure if the reduction from that to partition is natural (Is it ?) $\endgroup$
    – Karan
    Commented Nov 26, 2012 at 5:32
  • $\begingroup$ Interesting. I actually hadn't seen a formulation that requires non-emptiness. In that case, I would reduce first to the original version (which allows empty sets). Pick a number $S'$ greater than the sum of absolute values and add it to each element. To account for this addition, append $n-1$ copies of $-S'$ to the list. Now make the target $S'$. $\endgroup$ Commented Nov 26, 2012 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.