/* SYNOPSIS: Find all subsets of coins totalling to amount.
 * - Mohsin Ahmed (mosh@cse.iitb.ernet.in) 1-10-93.
 * GPL(C) Mohsin Ahmed, http://www.cs.albany.edu/~mosh                   
*/

/*
 * @ch_all( Amount:in, CoinList:in ) 
 * TopCallEg: ch_all( 100, [50,25] ) 
 * Gives all subsets of coins that add upto amount.
*/

ch(M,[M|_],M).
ch(A,[_|R],L) :- ch(A,R,L).
ch(A,[C|R],C+L) :-
	A >= C, A1 is A - C,
	ch(A1,[C|R],L).
ch_all( M, L ):-
	ch( M, L, A ), write( A ), nl, fail.
/*=== Partition integer N into smaller integers.
 TopCallEg: part( 10 ).
 @part( N:integer:in )
   gives all subsets of integers that add to N.
   Uses ch_all from above.
*/
part( N ) :- part( N, [1] ).
part( N, [N|L] ):-
	ch_all( N, [N|L] ).
part( N, [X|Y] ):-
	X < N, Z is X+1, part( N, [Z,X|Y] ).
/*=== Count all Solutions to coin change problem.
 TopCallEg: cc_all( 100, [50,25] ).
 @cc( Case:in, Amount:in, CoinList:in, NumberOfSolutions:out )
 @dd(          Amount:in, CoinList:in, NumberOfSolutions:out )
 */
cc(c,A,[C1|R],S, NS) :-
	A >= C1, A1 is A - C1,
	dd(A1,[C1|R],S+C1, NS).
cc(b,A,[_|R],S,NS) :-
	dd(A,R,S,NS).
cc(None,_,_,_,0).
dd( 0, _, S, 1  ):- write( S ), nl.
dd( A, L, S, NS ):-
	cc(a,A,L, S, NS1),
	cc(b,A,L, S, NS2),
	cc(c,A,L, S, NS3),
	NS is NS1 + NS2 + NS3.
cc_all( A, L ):-
	dd( A, L, 0, NS ),
	write('Num of Sols: '), write( NS ), nl.
/*======================================================*/