在Erlang中查找子集，请帮助我优化解决方案

Question

全面披露。这是一个面试/预先筛选的问题，我在面试中没能解决。为了自己的利益，我决定在二郎中实现它。

以下是问题陈述：

您必须找到数组的子集数，其中最大的数是剩余数的总和。例如，对于的输入：1、2、3、4、6

子集将是

1+2=3

1+3=4

2+4=6

1+2+3=6

以下是我的解决方案：

% 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)].

下面是一个运行示例：

示例：

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

问题

1. 亲爱的Erlangers（Erlangists？）对你来说，这看起来像规范的Erlang吗
2. 有没有更好的方式来表达我的所作所为
3. 有没有一个全面清洁的解决方案（这是一种蛮力）

谢谢！

Answer 1

这是一个外观更优雅的版本。

在这个版本中，我只假设正数，希望能加快速度。此外，我有点累，所以它可能有一些小的拼写错误，但基本上是正确的：）

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).    

我不确定这能加快多少，因为我怀疑背包问题会简化为这个问题。

Answer 2

这似乎是您的算法：

1. 生成所有组合（2^n）
2. 对每组组合求和（n）
3. 在列表中搜索每个总和（n）

看起来是n*2^n。我认为这是计算方面的最快速度，因为你必须尝试列表中每个数字的所有组合的顺序。也许有人能纠正我的错误。

然而，您的空间效率似乎是2^n，因为它存储所有组合，这是不必要的。

这就是我想到的，它只积累结果：

1. 对于每个项目，在列表的其余部分中搜索与其相加的组合
2. 为了找到组合，请从目标数字中减去列表的第一个数字，然后在列表的其余部分搜索加起来就是差值的组合

-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).

输出：

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