3 ms·
Though I don't have a proof this smells like NP to me. For a set of size |n| the search space is |2^n| and there may be no combination that sums up to the targe
by brudgers 8y ago
Though I don't have a proof this smells like NP to me. For a set of size |n| the search space is |2^n| and there may be no combination that sums up to the target so naively the all |2^n| combinations have to be checked.
If my intuition that it is in NP is correct, then the most efficient searches will require analysis of the Set and Target to understand the ways in which the are not random, because there is no generally fast algorithm for problems in NP with random data. But again, I could be wrong and the problem could be polynomial.
Once there is actual data, heuristics might make it obvious that there is no solution:
Target == 0
Domain == {1}
Or allow removal of some values. Assuming a O(n log n) sort of the set into an array. O(n log n) is rounding error on O(2^n) or virtually free. Particularly for problems of interesting size.
Target == 3
Domain == {2, 4, 5, 1}
The more we know about the data, the more we can prune the search space:
Target == 118
Domain == {3,6,9,12...}