Given the following problem:

Input: A set of disjoint sets $s_1, s_2, \dots s_n$, and an integer $K$

Question: Is there a set A with $|A|= n$ and $|s_i \cap A| = 1$ for all i from 1 to n, s.t. $\sum_{a \in A}a=K$?

The problem is obviously weakly NP-hard (reduction from subset sum), but I was wondering whether it might be strongly NP-hard?

  • 1
    $\begingroup$ Assuming that you by "disjoint" mean that no number appears in more than one set: If you are familiar with the pseudo-polynomial algorithm for Subset Sum (or related problems like Knapsack), then you should have little problem coming up with one for this problem as well. $\endgroup$
    – Highheath
    Commented May 2 at 19:45


Your Answer

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