math - Finding subsets in Erlang, please help me optimize the solution -

full disclosure. interview/prescreen question failed solve during interview. decided implement in erlang own benefit.

here's problem statement:

you must find number of subsets of array largest number sum of remaining numbers. example, input of: 1, 2, 3, 4, 6

the subsets be

1 + 2 = 3

1 + 3 = 4

2 + 4 = 6

1 + 2 + 3 = 6

here's solution:

% credit: http://stackoverflow.com/questions/1459152/erlang-listsindex-of-function index_of(item, list) -> index_of(item, list, 1). index_of(_, [], _)  -> not_found; index_of(item, [item|_], index) -> index; index_of(item, [_|tl], index) -> index_of(item, tl, index+1).  % find sums findsums(l) ->     permutations=generateallcombos(l),     lists:filter(fun(ll) -> case index_of(lists:sum(ll), l) of                     not_found -> false;                     _ -> true                 end         end, permutations).   % generate combinations of size 2..legnth(l)-1 generateallcombos(l) ->     newl=l--[lists:last(l)],     sizes=lists:seq(2,length(newl)),     lists:flatmap(fun(x) -> simplepermute(newl,x) end, sizes).  % generate list of permutations of size r list l simplepermute(_,r) when r == 0 ->     [[]];  simplepermute(l,r) ->     [[x|t] || x <- l, t<-simplepermute(lists:nthtail(index_of(x,l),l),r-1)]. 

here's example run:

example:

18> maxsubsetsum_app:findsums([1,2,3,4,6]). [[1,2],[1,3],[2,4],[1,2,3]] 

questions

1. dear erlangers (erlangists?) canonical erlang you?
2. is there better way did?
3. is there cleaner on solution (this quite brute force).

thank you!

it seems algorithm:

1. generating combinations (2^n)
2. summing each set of combinations (n)
3. searching list each sum (n)

that looks it's n*2^n. think that's fast can go in terms of computation, since have try on order of combinations every number in list. maybe can correct me on that.

however, space efficiency seems 2^n, since stores combinations, unnecessary.

this came with, accumulates results:

1. for each item, search rest of list combinations add it.
2. in order find combinations, subtract first number of list target number, , search rest of list combinations add difference.

-module(subsets).  -export([find_subsets/1]).   find_subsets(numlist) ->   reversesorted = lists:reverse(lists:sort(numlist)),   find_each_subset(reversesorted, []).  find_each_subset([], subsets) ->   subsets; find_each_subset([first | reversesorted], subsets) ->   [ { first, recurse_find_subsets(first, reversesorted, [])} | find_each_subset(reversesorted, subsets)].  recurse_find_subsets(_target, [], sets) ->   sets; recurse_find_subsets(target, [target | _numbers], []) ->   [[target]]; recurse_find_subsets(target, [first | numbers], sets) when target - first > 0 ->   subsets = recurse_find_subsets(target - first, numbers, []),   newsets = lists:map(fun(subset) -> [ first | subset] end, subsets),   recurse_find_subsets(target, numbers, lists:append(newsets, sets)); recurse_find_subsets(target, [_first | numbers], sets) ->   recurse_find_subsets(target, numbers, sets). 

output:

5> subsets:find_subsets([6,4,3,2,1]). [{6,[[3,2,1],[4,2]]},{4,[[3,1]]},{3,[[2,1]]},{2,[]},{1,[]}]