# Black box with O(n) calls

Let's say a procedure called 'decision(x,q)' is available as a 'black box' X is the input set and Q is a real number Q.

I need to design an algorithm that reports "yes" if there exists a subset of X whose total sum is = Q otherwise, it reports "no".

Running time is not an issue, it just needs to have all actual numbers in the subset and it can't make more than O(n) calls to the procedure.

I believe this can be solved with dynamic programmming.

I believe you have misunderstood the question. You are given a black box that can answer queries of the form "does $X$ have a subset summing to $Q$", and you need to construct an algorithm that given $X$ and $Q$, finds a subset summing to $Q$ if one exists.

Here is a hint:

Choose an arbitrary $x \in X$. Ask the black box whether there is a subset of $X - x$ summing to $Q - x$.

• Thank you. Could I approach this with a simple knapsack approach? Commented Nov 5, 2014 at 3:13
• I don't know what a simple knapsack approach is, but if you succeed, then it's possible. Commented Nov 5, 2014 at 3:14