Finding subsets in Erlang, please help me optimize the solution

Question

Full disclosure. This was an interview / preliminary question that I could not resolve during the interview. I decided to implement it in Erlang to my advantage.

Here's the problem statement:

You should find the number of subsets of the array, where the largest number is the sum of the remaining numbers. For example, to enter: 1, 2, 3, 4, 6

subsets would be

1 + 2 = 3

1 + 3 = 4

2 + 4 = 6

1 + 2 + 3 = 6

Here is my 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 all 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 a list of permutations of size R from 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 is an example:

Example:

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

Questions

• Dear Erlangists (Erlangists?) Does this look like a canonical Erlang?
• Is there a better way to say what I did?
• Is there a cleaner solution (this is a pretty brute force).

Thanks!

Answer 1

This seems to be your algorithm:

• Create all combinations (2 ^ n)
• Summation of each set of combinations (n)
• List search for each sum (n)

It looks like n*2^n . I think that as fast as you can go in terms of calculations, since you need to try in order of all the combinations for each number in the list. Maybe someone can fix me about this.

However, your cosmic efficiency seems 2^n , since it stores all the combinations that you don't need.

This is what I came up with that only accumulates the results:

• For each item, search the rest of the list for combinations that add to it.
• To find combinations, subtract the first number of the list from the target number and find the rest of the list for combinations that make up the 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,[]}] 

Answer 2

Here is a more elegant version.

In this version, I assume only positive numbers with the hope of some speed. Also, I'm a little tired, so I might have small typos, but mostly correct ones :)

 get_tails([]) -> []; get_tails([_]) -> []; get_tails([X:XS]) -> [[X:XS],get_tails(XS)]. get_sums([]) -> []; get_sums([_]) -> []; get_sums([X:XS]) -> [get_sums_worker(X,XS):get_sums(XS)] get_sums_worker(S,_) when S < 0 -> []; get_sums_worker(S,_) when S == 0 -> [[]]; get_sums_worker(S,[X:XS]) when S > 0 -> get_sums_worker(S, XS) ++ [[X:L] || L <- get_sums_worker(S - X, XS)]. sums(A0) -> A = lists:reverse(lists:sort(A0)), B = get_tails(A), lists:flatmap(fun get_sums/1, B). 

I am not sure how much this can be accelerated, since I suspect that the problem with the backpack comes down to this question.