给定一个整数列表和一个整数 k，return k 是否可以构建为该列表中任何数字的总和或其乘法

Question

我的一个朋友在面试中被要求解决以下问题，但没有成功。我想自己尝试一下，但乍一看似乎比我想象的要难，所以 Stack 社区，请帮助 :)

Given a list of integers and an integer k, return whether k can be built as a sum of any numbers from that list or a sum of any multiplications of these numbers.

ex: for given [2,3,4] and k = 13 for the following found combinations method should return true.
1) 2, 2, 2, 2, 2, 3
2) 2, 2, 2, 3, 4
3) 2, 2, 3, 3, 3
4) 2, 3, 4, 4
5) 3, 3, 3, 4

我已经尝试过的是这样的：

List<Integer> inputList = new List<Integer>{
        2, 3, 4
};
Integer k = 13;
Boolean result = false;

for (Integer i = 0; i < inputList.size(); i++) {
    for (Integer j = 0; j < inputList.size(); j++) {
        if (k >= inputList.get(i) && Math.mod(k - inputList.get(i), inputList.get(j)) == 0) {
            result = true;
            break;
        }
    }
    if (result == true) {
        break;
    }
}

return result;

但不幸的是，这不是正确的解决方案，因为它没有考虑这种情况，当 k 不能被输入列表中的每个数字整除，但仍然有两个以上的数字（或它们的乘法）加在一起可以结果给定k。考虑质数，例如：[17, 53, 97] 和 k=167。两者都不是k除法器，但加起来的结果是167.

有什么想法可以解决吗？我正在考虑递归，但我也被告知，这可以用更简单的方法解决，只需大约 10 行代码。

PS：我在 APEX 中编写了我的代码片段，这是一种简化的 java。它没有流，向量，广泛 collections 等，但任务更像是一个数学问题，因此将不胜感激任何形式的帮助！

Answer 1

我认为乘法无关紧要，因为加法可以达到相同的结果。试试这个 DP 方法

L=[1]+[0]*k
for n in nums:
    for m in range(n,k+1):
        L[m]+=L[m-n]
print(L[-1]>0) #L[-1] is the number of combinations you can reach k by addition

给定一个整数列表和一个整数 k，return k 是否可以构建为该列表中任何数字的总和或其乘法

Given a list of integers and an integer k, return whether k can be built as a sum of any numbers from that list or their multiplications

math

recursion

loops

nested-loops