import java.util.ArrayList;

import java.util.Vector;

public class KnapsackComplete_Recursive implements IKnapsackComplete {

	public ArrayList<Integer> getSolution(Vector<Integer> weights, int last,
			int k) {

		ArrayList<Integer> s;

		if (last == 0) {
			if (weights.elementAt(last) == k) {
				s = new ArrayList<Integer>();
				s.add(weights.elementAt(last));
				return s;
			} else
				return null;
		}

		s = getSolution(weights, last - 1, k);
		if (s != null)
			return s;
		else {
			if (weights.elementAt(last) == k) {
				s = new ArrayList<Integer>();
				s.add(weights.elementAt(last));
				return s;
			} 
			else 
				if (k - weights.elementAt(last) > 0) {
					s = getSolution(weights, last - 1, k - weights.elementAt(last));
				    if (s != null) {
					    s.add(weights.elementAt(last));
					    return s;
				    }
				    else 
				    	return null;
			} else
				return null;
		}
	}
}