Illustrate the dynamic programming in subset_sum_problem

subset_sum_problem_exp_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#Exponential_time_algorithm
%%

main(_) ->
	L = [1,-3,2,4],
%	L = [ -19 | lists:duplicate( 19,1) ],
%	L = lists:duplicate( 20,1 ), %%1m21s
%	L = lists:duplicate( 30,1 ), %%TIMEOUT >3h

	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([H|T]=L, X) ->
	io:format("DEBUG: L:~p X:~p ~n",[L,X]),
	case H==X of
		true ->
			[[H]];
		false ->			
			Subsets1 = subset_with_sum_equal_x(T,X),
			case Subsets1 of
				[] ->
					Subsets2 = subset_with_sum_equal_x(T,X-H),
					lists:map( fun(Subset) ->
									   [H|Subset]
							   end, Subsets2);
				_ ->
					Subsets1
			end
	end.