World's most popular travel blog for travel bloggers.

# Black box with O(n) calls

, ,
Problem Detail:

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.

###### Answered By : Yuval Filmus

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$.