要继续 awesomo 的回答......如果我们可以假设数字已排序，那么对于给定的 k，我们可以比 O(n^k) 更好；只需取大小为 (k-1) 的所有 O(n^(k-1)) 子集，然后在剩余部分中进行二进制搜索，以找到一个数字，当加到第一个 (k-1) 个数字时，会得到目标值。这是 O(n^(k-1) log n)。这意味着复杂度肯定比那个小。
实际上，如果我们知道 k=3 时复杂度为 O(n^2)，那么对于 k>3，我们甚至可以做得更好：选择所有 (k-3) 子集，其中有 O(n^(k-3)) 个子集，然后在剩余元素中以 O(n^2) 解决问题。这是 k >= 3 时的 O(n^(k-1))。
但是，也许你可以做得更好？我会考虑一下这个问题。
编辑：我最初打算添加很多关于这个问题的不同看法，但我决定发布缩写版。我鼓励其他发帖人看看他们是否认为这个想法有任何价值。分析很艰难，但它可能足够疯狂，可以运行。
我们可以利用固定的 k 和奇数和偶数数字之和的特定行为，定义一个递归算法来解决这个问题。
首先，修改问题，使列表中既有偶数又有奇数（如果全部是偶数，则可以通过除以二来实现；如果全部是奇数，则可以通过减去 1 和 k 的目标和，然后根据需要重复）。
接下来，利用偶数目标和只能通过使用偶数个奇数数字达到，奇数目标和只能使用奇数个奇数数字达到的事实。生成适当的奇数子集，并使用偶数数字、检查的奇数数字子集之和减去总和以及 k 减去奇数数字子集的大小调用递归算法。当 k=1 时，进行二进制搜索。如果 k > n（不确定是否会发生），则返回 false。
如果你有很少的奇数数字，这可能允许你非常快地挑选出必须成为获胜子集的术语，或者丢弃不能成为获胜子集的术语。你可以通过使用减法技巧将具有大量偶数数字的问题转换为具有大量奇数数字的等效问题。因此，最坏情况肯定是当偶数数字和奇数数字的数量非常相似时......这就是我现在的情况。这个问题的无用宽松上限比暴力搜索多几个数量级，但我觉得这可能至少和暴力搜索一样好。欢迎讨论！
编辑2：上述内容的示例，仅供说明。
{1, 2, 2, 6, 7, 7, 20}, k = 3, sum = 20.
Subset {}:
{2, 2, 6, 20}, k = 3, sum = 20
= {1, 1, 3, 10}, k = 3, sum = 10
Subset {}:
{10}, k = 3, sum = 10
Failure
Subset {1, 1}:
{10}, k = 1, sum = 8
Failure
Subset {1, 3}:
{10}, k = 1, sum = 6
Failure
Subset {1, 7}:
{2, 2, 6, 20}, k = 1, sum = 12
Failure
Subset {7, 7}:
{2, 2, 6, 20}, k = 1, sum = 6
Success
k=1，下限将是O(n)（您不能假设输入已排序）。 - awesomo