import java.util.Vector;

public class KnapsackSimple_Recursive implements IKnapsackSimple {

	public boolean hasSolution(Vector<Integer> weights, int last, int k) {
		if (last == 0) { // only one candidate item in weights
			if (weights.elementAt(last) == k)
				return true;
			else
				return false;
		}

		// more than one candidate item in weights

		if (hasSolution(weights, last - 1, k))
			return true;
		else {
			if (weights.elementAt(last) == k)
				return true;
			else if (k - weights.elementAt(last) > 0)
				return hasSolution(weights, last - 1,
						k - weights.elementAt(last));
			else
				return false;
		}
	}
}