% Subset of a list summing to a given number
% Memoised version

:- dynamic recorded_subsetsums/3.

% subsetsum_memo(List,Sum,Result)
%
% succeeds if List is a list and Result is a
% subset of that list summing to Sum

subsetsum_memo(List,Sum,Result) :-
   recorded_subsetsums(List,Sum,All), !,
   write(memo-for-List-Sum), nl,
   member(Result,All).
subsetsum_memo(List,Sum,Result) :-
   findall(X,subsetsum(List,Sum,X),All),
   assert(recorded_subsetsums(List,Sum,All)),
   member(Result,All).

subsetsum([],0,[]).
subsetsum([X|List],Sum,[X|Subset]) :-
   Newsum is Sum-X, Newsum >= 0,
   subsetsum_memo(List,Newsum,Subset).
subsetsum([_|List],Sum,Subset) :-
   subsetsum_memo(List,Sum,Subset).

member(X,[X|_]).
member(X,[_|L]) :- member(X,L).
