java - 从数字列表中找到所有不同总和的算法

Question

示例输入:

4 6 4 3 2 2 1 1

第一个数 = A 总数，T (T < 1000)

第二个数字 = 数字的个数，S (S <= 12)

以下 S 个数字 = 数字的值(每个值 < 100)。 (可以重复，输入按非递增顺序给出)

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

因此，该输入的样本输出将是:

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

我的想法是 1 对 1 地遍历列表，找到一个数字与不同数字的所有组合，直到数字列表的大小 - 已计算的数字数。您从每个组合中创建一个列表，并将该列表添加到列表的 HashSet(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)}