an interview question

knapsack01.m

% problem: we have a result, and many elements, find all combinations that sum up to the result


function sol = knapsack01(maxCapacity, items)
 
% knapsack problem with variables in {0,1}
 
% Naive solution is O(n!), knapsack implementation is O(n*m) where n is 
% items length and m is weights length
 
% test cases
% all(knapsack01(7406,[2275 5933 3422 2721 1709 10099]) == [1709 3422 2275])
% knapsack01(17,[1 7 8 9 11 12 15])
 
sm=zeros(length(items)+1, maxCapacity+1);
km=nan(length(items)+1, maxCapacity+1);
km(1,:) = false;
 
for i=1:length(items)
   item = items(i);
   for capacity=0:maxCapacity
       if item<=capacity && sm(i,capacity-item+1) + item > sm(i,capacity+1)
           sm(i+1,capacity+1) = sm(i,capacity-item+1)+item;
           km(i+1,capacity+1)= true;
       else
           sm(i+1,capacity+1) = sm(i,capacity+1);
           km(i+1,capacity+1)= false;
       end
   end
    
end
 
capacity = maxCapacity;
sol=[];
for i = length(items):-1:1
   item = items(i);
   if km(i+1,capacity+1)
       sol = [sol item];
       capacity = capacity-item;
   end
end