In duplicate subset sum problem (DuSSP), we are given a multiset $\{a_1,a_2,\ldots,a_n\}$ where some of the $a_i$ are duplicates. We can assume that $a_1\leq a_2\leq \cdots\leq a_m.$ We are also given a target $s$. The problem is to find a subset of $\{a_1,a_2,\ldots,a_n\}$ that sum up to $s$.

In distinct subset sum problem (DiSSP), we are given a set $\{b_1,b_2,\ldots,b_n\}$ where all the elements $a_i$ are distinct. We are also given a target $t$. The problem is to find a subset of $\{b_1,b_2,\ldots,b_n\}$ that sum up to $t$.

Given an instance of DuSSP, create an instance of DiSSP such that DuSSP is solved iff DiSSP is solved.

What I did so far is. Let $b_i=a_i+i$, in this way we guarantee that all the elements $b_i$ are distinct. I cannot create $t$...!

What I said is the following, given a subset $S$ of $\{a_1,a_2,\ldots,a_n\}$ such that $\sum_{i\in S}a_i=s$. We prove that $$\sum_{i\in S}a_i=s\iff\sum_{i\in S}b_i=s+\sum_{i\in S}i.$$

So, $t=s+\sum_{i\in S}i$, but can we choose $t$ to depend on the solution set $S$?

Is this reduction correct? Why or why not?

  • 1
    $\begingroup$ The way to tell whether your reduction is correct is to prove it correct. Have you tried to do that? $\endgroup$ – D.W. Nov 8 '19 at 23:46
  • 1
  • 2
    $\begingroup$ What @D.W. is getting at is that you have not included any attempt of the proof itself. As such, it's hard to tell where you're stuck and how to help you. We are not in the business of doing homework for people, so posting a full answer is usually not what's going to happen. That's also an issue of limited time; the more focussed your question, the more efficient to answer it is. $\endgroup$ – Raphael Nov 10 '19 at 11:38
  • 2
    $\begingroup$ I'll also add that the first part of the question reads like a literal quote from an exercise sheet. Please give a full reference. $\endgroup$ – Raphael Nov 10 '19 at 11:39
  • 2
    $\begingroup$ Possible duplicate of Does Subset Sum allow multisets? $\endgroup$ – narek Bojikian Nov 10 '19 at 13:37

Your Answer


Browse other questions tagged or ask your own question.