Should check all $2^n$ possibilities in array?
The query complexity of your problem, which is the number of oracle calls that any correct algorithm needs to make, is $2^n-1$ (or even $2^n$, if the oracle is allowed to return "No" on all inputs, in which case the answer to your problem is "Infeasible"). This assumes your oracle is a black box. When your oracle is given explicitly, the complexity of the problem could depend on the oracle. For the primality oracle, your problem is likely hard, but this could be challenging to prove since the additive properties of primes are not well-understood.

Indeed, suppose that you have an algorithm solving your problem on arrays of length $n$ using less than $2^n-1$ oracle calls in the worst case. Run it on the array $1,2,4,\ldots,2^{n-1}$. Whenever the oracle asks a question, always return "No" (i.e., cannot be used). When the algorithm has finished, there are at least two sets $S,T$ that have not been queried. There we can consider two oracles, one that says "Yes" only on $\Sigma(S)$ (the sum of elements in $S$) and the other that says "Yes" only on $\Sigma(T)$. By construction, $\Sigma(S) \neq \Sigma(T)$, and so the correct answer is different in both cases. However, the algorithm cannot distinguish between the two oracles, and so its output will be wrong for at least one of these two oracles.

If we allow the oracle to return "No" on all inputs, then we can get a contradiction even given an algorithm that makes exactly $2^n-1$ oracle calls in the worst case. Running it on the same array and answering every query negatively, there is always a set $S$ which has not been queried, and the algorithm cannot distinguish between the oracle which answers "Yes" only on $S$ (in which case the answer is $S$) and the oracle which always answers "No" (in which case the answer is "Infeasible").