Search code examples
dynamicprologmembership

dynamically check membership swi-prolog

Given a list of natural numbers List I want to check if the sums of the elements of each subset are distinct. Initially I used this code

distinctSubsetSums(List,Sums) :- findall(Sum,(subset(Sub,List),sum_list(Sub,Sum)),Sums), all_distinct(Sums).

But I think there exists a better solution since with my code I found all the sums of all the possibile subsets and then I check if they are distinct. I think there is a way to check dynamically if a sum has been already calculated and then return false without searching for all the subsets.

Can anyone help me?

Solution 
  • subset_sums(List,Sums) :-
  sum_subset(List,[],[],Sums).

sum_subset([I|Is],Js,Sums0,Sums) :-
  sum_subset(Is,Js,Sums0,Sums1),
  sum_subset(Is,[I|Js],Sums1,Sums).
sum_subset([],Js,Sums0,Sums) :-
  sum_list(Js,Sum),
  \+ member(Sum,Sums0),
  Sums = [Sum|Sums0].