Prolog Code that reachs a combination of numbers that sums up to a goal

Question

I found this code and i just need to understand its idea and how is it working. it outputs a list of numbers that sums up to a specific number (goal)

example for a run:

?- threeSum([3,8,9,10,12,14],27,Output).
   Output = [3, 10, 14] ;
   Output = [8, 9, 10] ;
   false.

and here is the code:

threeSum([H|T], Goal, Output):-
    solve(Goal,[H|T],Output).

subset([], []).
subset([H|T], [H|T1]):-
  subset(T,T1).
subset([_|T],T1):-
  subset(T, T1).

solve(MaxVal,Lin,Lout):-
    subset(Lin,Lout),
    sumlist(Lout,Val),
    Val = MaxVal.

Answer 1

subset/2 has three different cases:

1. subset([], []).

   the base case: if the input list is empty, it returns also an empty list

2. subset([H|T], [H|T1]):- subset(T,T1).

   (this case is selected by default if the list is not empty): the first element of the output list is set to be equal to the first element of the input list. The tail of the list is then calculated recursively.

3. subset([_|T],T1) :- subset(T, T1).

   This case is selected, if the upper cases fail somehow: The head element of the input list is ignored and the tail is again calculated recursively.

The last part of solve/3 just sums the values of Lout, compares it to the goal value, and if it fails, it backtracks, i.e. tries to find another solution for subset/2.

At first, the second case of subset/2 is selected until the input list is empty. So after the first subset([3,8,9,10,12,14], Lout) in solve/3, Lout becomes [3,8,9,10,12,14]. The sum of this list is not equal to MaxVal, so it fails and the backtracking is initiated. Now the last call of subset/3 with a choice point, i.e. subset([14], Lout) fails, such that the third case of subset/3 is called. Therefore, after the first backtracking step, the value of Lout in subset([3,8,9,10,12,14], Lout) is now [3,8,9,10,12]. This is again not equal to MaxVal and the next backtracking is started. This goes on and on until Val = MaxVal is true.