Output is a list of three elements [A,B,C] taken from items that together add up to goal. The Output inside the items list in that order

Question

`three Sum([1,2,3,4,5,6,7,8,9],12,Output).
 Output=[1,2,9];
 Output=[1,3,8];
 Output=[1,4,7];
 Output=[1,5,6];
 Output=[2,3,7];
 Output=[2,4,6];
 Output=[3,4,5]`

we should make result = summation 3 elements sorted ascendingly from list

Answer 1

This is fundamentally a matter of finding all the combinations of n things taken k at a time. To do that is pretty simple:

combination( 0 , _ , []    ) :- !.
combination( N , L , [C|Cs] ) :-
    N > 0,
    N1 is N-1,
    select(L,C,L1),
    combination(N1, L1, Cs).

select( [H|T] , H, T ) .
select( [_|T] , H, R ) :- select(T,H,R) .

once you have that, then it is a matter of wrapping it up nicely:

combination_sum( Xs, K, V, Ys ) :-
  sort(Xs,X0), % orders the list, making it a proper set by removing duplicates
  length(Xs,L),
  between(1,L,K), % ensures K has a sensible value (and allows K to be unbound
  combination(K,X0,Ys),
  sum_of(Ys,V).

sum_of( Xs , S ) :- sum_of(Xs,0,S).

sum_of( []     , S , S ).
sum_of( [X|Xs] , T , S ) :- T1 is T+X, sum_of(Xs,T1,S) .

That gives you the generic, flexible solution: you can solve the problem for any given sized subset.

Note also that you may, should you choose, leave K or V unbound (or both, for that matter), and it will return all solutions for the given constraints:

• combination_sum( [1..n], K, V, L ) yields all combinations of any length and their sum
• combination_sum( [1..n], K, 12, L ) yields all combinations of any length that sum to 12.
• combination_sum( [1..n], 3, V, L ) yields all combinations of length 3 that sum to any value.
• combination_sum( [1...n], 3, 12, L ) yields all combinations of length 3 that sum to 12.

Then, just wrap that for your specialized use case:

sum_three(Xs,V,Ys) :- combination_sum(Xs,3,V,Ys).

Answer 2

three_sum(Lst, Total, [One, Two, Three]) :-
    % Using msort, to sort without removing duplicates
    msort(Lst, LstSorted),
    select_remainder(One, LstSorted, Lst1),
    select_remainder(Two, Lst1, Lst2),
    select_remainder(Three, Lst2, _),
    Total is One + Two + Three.

select_remainder(Elem, [H|T], RemainderForward) :-
    select_remainder_(T, H, Elem, RemainderForward).

select_remainder_(T, H, H, T).
select_remainder_([H|T], _, Elem, R) :-
    select_remainder_(T, H, Elem, R).

Result in swi-prolog:

?- time(findall(Lst, three_sum([1,2,3,4,5,6,7,8,9], 12, Lst), Lsts)).
% 278 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 1220471 Lips)
Lsts = [[1,2,9],[1,3,8],[1,4,7],[1,5,6],[2,3,7],[2,4,6],[3,4,5]].