Search code examples
prolog

Define the relation `subsum(Set,Sum,Subset)`


I have a problem.

Define the relation subsum(Set,Sum,Subset) such that Set is a multiset of numbers expressed using lists, Subset is a subset of Set, and Sum is the union of the elements of Subset. The following results are obtained.

?- subsum([1,2,5,3,2],5,Sub).
Sub = [1, 2, 2] ;
Sub = [2, 3] ;
Sub = [5] ;
Sub = [3, 2] ;
false.
?-

The answers must not use any relationship other than the answer.

My answer is:

subsum([], 0 ,[]).
subsum([_ | Xs], Sum, Ys) :- subsum(Xs, Sum, Ys).
subsum([X | Xs], Sum, [X | Ys]) :- subsum(Xs, Sum - X, Ys).

But this code does not work as I expected. Could you give me some hints?


Solution

  • Could you give me some hints?

    Trace the code; e.g. from SWISH:

    Example trace from SWISH

    Your first line is subsum([], 0 ,[]). which can only match if the desired sum is 0 but if there are no elements which sum to the target, there won't be a 0 in the middle when it's called.


    subsum(Xs, Sum - X, Ys) run this:

    Sum = 5,
    Y = 2,
    writeln(Sum - Y)
    

    What do you expect it to write? What does it actually write?