Restricted partitions?

211 Views Asked by At

Suppose I have an integer N and i want to partition it, it must only involve numbers in set $S$ and the number should appear only once.
For example if $N = 12$ and $S = \{3, 5, 7\}$ the answer should be $\{5, 7\}$ (order does not matter).
What is the name of this problem ? Does it have a solution in polynomial time ?
Because it sounds like subset sum problem more than integer partition.

1

There are 1 best solutions below

2
On BEST ANSWER

This is likely an open problem.

The problem of determining if a CNF formula has exactly one satisfying assignment is known to be CO-NP hard, and thus not known to be NP-Complete (and an affirmative answer to the latter that would imply co-NP=NP which is open).

I would expect the same for 3SAT and based on its reduction to SUBSET SUM, I would expect your problem to be open too.

Sorry, don't know a name, but perhaps UNIQUE-SUBSET-SUM might be appropriate.