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
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Nov 8 '19 at 23:47
  • 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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.