Illustrate the dynamic programming in subset_sum_problem

subset_sum_problem_poly_time.erl

#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname subset_sum_problem

%%
%% Illustrate the dynamic programming in subset_sum_problem:
%% http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution 
%%

main(_) ->
	L = [1,-3,2,4],
%	L = [1 | lists:append( lists:duplicate(20, -20) , lists:duplicate( 19,1) )], %%2s
%	L = lists:append( lists:duplicate(40, -200) , lists:duplicate( 20,10) ), %%

	SS = subset_with_sum_equal_zero(L),
	[ io:format("Subsets: ~p~n",[S]) || S<-SS ].

subset_with_sum_equal_zero(L) ->
	subset_with_sum_equal_x(L, 0).

subset_with_sum_equal_x([I],X) ->
	case I==X of
		true ->
			[[I]];
		false ->
			[]
	end;

subset_with_sum_equal_x(L,X) ->
	io:format("DEBUG: L: ~p ~n",[L]),
	L1 = lists:sort(L),
	{Negs,Poss} = lists:splitwith(fun(I) -> I < 0 end, L1),
%	io:format("DEBUG: NEG:~p POS:~p~n",[Negs,Poss]),

	SumNeg=lists:sum(Negs),
	SumPos=lists:sum(Poss),
	if X > SumPos orelse X < SumNeg ->
			[];
	   true ->			
			M = make_matrix(L, SumNeg, SumPos),
			io:format("DEBUG: MATRIX: ~p~n",[M]),
			case find_subset_sum_equal_x(L, M, SumNeg, X) of
				[] ->
					[];
				S ->
					[S]
			end
	end.

make_matrix([H|T], LB, UB) ->
	Row = first_row(H, LB, UB),
	make_matrix( T, LB, UB, [Row]).

make_matrix([], _, _, M) ->
	lists:reverse(M); 
	
make_matrix([H|T], LB, UB, [Prev|_] = M) ->
	Row = make_row(H, Prev, LB, UB),
	make_matrix(T, LB, UB, [Row|M]).

first_row(H, LB, UB) ->
	Row = lists:append(lists:duplicate(H-LB,0), [1|lists:duplicate(UB-H,0)]),
	list_to_tuple( Row ).
	
make_row(H, Prev, LB, UB) ->
	make_row(H, Prev, LB, UB, 0, UB-LB+1,[]).

make_row(_, _, _, _, _, 0, Row ) ->
	list_to_tuple( lists:reverse(Row) );

make_row(H, Prev, LB, UB, Iter1, Iter2, Row ) ->
	S = LB+Iter1,
	case S-H of
		0 ->
			make_row(H, Prev, LB, UB, Iter1+1, Iter2-1, [1|Row]);
		D ->			
			case element(Iter1+1, Prev) of
				1 ->
					make_row(H, Prev, LB, UB, Iter1+1, Iter2-1, [1|Row]);
				_ ->
					case D >= LB andalso D =< UB 
						andalso element( D-LB+1, Prev) of
						1 ->
							make_row(H, Prev, LB, UB, Iter1+1, Iter2-1, [1|Row]);
						_ ->
							make_row(H, Prev, LB, UB, Iter1+1, Iter2-1, [0|Row])
					end
			end
	end.

find_subset_sum_equal_x(L, M, SumNeg, X) ->
	find_subset_sum_equal_x(lists:reverse(L), lists:reverse(M), SumNeg, X, []).

find_subset_sum_equal_x([H], [NowRow], SumNeg, X, S) ->
	Num = X-SumNeg+1,
	case element(Num, NowRow) of
		1 ->
			[H|S];
		_ ->
			[]
	end;

find_subset_sum_equal_x([H|T], [NowRow,PrevRow|M], SumNeg, X, S) ->
	Num = X-SumNeg+1,
	case {element(Num, NowRow), element(Num, PrevRow)} of
		{1,0} ->
			find_subset_sum_equal_x(T, [PrevRow|M], SumNeg, X-H, [H|S]);
		{1,1} ->
			find_subset_sum_equal_x(T, [PrevRow|M], SumNeg, X, S);
		{0,_} ->
			[]
	end.