一种从数字列表中查找所有不同总和的算法

Question

样本输入：

4 6 4 3 2 2 1 1

第一个数字=总数，T（T <1000）

第二个数字=数字数，S（S <= 12）

跟随S数=数字的值（每个值<100）。 （重复可能发生，输入以非递增顺序给出）

我的工作是使用列表中添加到T的数字找到所有“不同的总和”。

因此，该输入的示例输出将是：

4
3+1
2+2
2+1+1

我的想法是逐个浏览列表，找到一个数字不同的数字的组合，最大为数字列表的大小 - 已经评估过的数字的数量。您可以从每个组合中创建一个List，并将List添加到HashSet of Lists（HashSet以防止重复）。

因此，您需要检查所有1,2,3,4,5和6大小的组合，然后选择4个然后所有1,2,3,4,5大小的组合与3一起，忽略4然后所有1,2,3,4大小的组合与2一起，忽略4和3

等等

1. 我不确定这个算法是否真的有效
2. 我在实施该算法时遇到了困难。我无法绕过如何循环结构以获得所需的组合。

Answer 1

你应该尝试递归解决方案。主要是你必须要考虑的是，对于每个数字，你可以将它包括在你的总和中，或者你不能。这意味着您正在构建数字的幂集，并将生成O(2^N)解决方案。

简要地说是伪代码：

def get_all_sums(arr, target):

    result = []

    def helper(index, current_arr, current_sum):

        # once you've gone over the arr you can return. If all your numbers are positive
        # you can also return early if the current_sum > target
        if index == len(arr): return

        # solution found - add it to the result
        if current_sum == target: result.append(current_arr)

        # include the current index
        helper(index + 1, current_arr + [arr[index]], current_sum + arr[index])

        # don't include the current index
        helper(index + 1, current_arr, current_sum)

    helper(0, [], 0)

    # sort and hash to get rid of duplicates; return a set
    return {tuple(sorted(i) for i in result)}

Answer 2

答案可以通过简单的递归找到，我将使用问题中的示例进行演示。

在第一级递归时，要解决的问题是

target=4 count=6 allowed={4,3,2,2,1,1} chosen={}

第一级选择循环中的每个唯一值，然后进行递归调用。所以来自第一级的递归调用是

target=0 size=5 allowed={3,2,2,1,1} chosen={4}
target=1 size=4 allowed={2,2,1,1} chosen={3}
target=2 size=3 allowed={2,1,1} chosen={2}
target=3 size=1 allowed={1} chosen={1}

这里的关键是允许值的数组在每个递归级别变小。只能使用遵循所选值的那些值。因此，例如，当第一级递归选择值3时，则只允许小于3的值。在重复的情况下，选择第一个副本，并将允许的值限制为剩余的重复项和任何较小的值。

---

在参数为的第二级递归时

target=0 size=5 allowed={3,2,2,1,1} chosen={4}

这是成功的基本情况：target为0.在这种情况下，将{4}添加到输出列表，因为这是一个解决方案。

---

在参数为的第二级递归时

target=1 size=4 allowed={2,2,1,1} chosen={3}

代码应该跳过2，因为2大于目标。所以唯一的递归调用是

target=0 size=1 allowed={1} chosen={3,1}

这又是基本情况，因此第三级递归会将{3,1}添加到输出中。

---

在参数为的第二级递归时

target=2 size=3 allowed={2,1,1} chosen={2}

会有两个递归调用

target=0 size=2 allowed={1,1} chosen={2,2}
target=1 size=1 allowed={1} chosen={2,1}

第一个是基本案例，因此将{2,2}添加到输出中。另一个递归调用最终会将{2,1,1}添加到输出中。

---

在参数为的第二级递归时

target=3 size=1 allowed={1} chosen={1}

有一个递归调用

target=2 size=0 allowed={} chosen={1,1}

这是失败的基本情况：target非零，size为0。

---

请注意，以这种方式解决问题时，只会生成唯一解决方案，因此无需删除重复的解决方案。

另请注意，最大递归深度由S确定，因此将S约束到相当小的数量（S <= 12合格为相当小）非常重要。