问题标签 [subset-sum]

给定一组未排序的n整数，返回所有大小为 k 的子集（即每个集合有 k 个唯一元素），总和为 0。

所以我给了面试官以下解决方案（我在GeekViewpoint上研究过的）。没有使用额外的空间，一切都完成了，等等。但当然，成本是解决方案中 O(n^k) 的高时间复杂度k=tuple。

但随后她提出了以下要求：

• 必须在答案中使用 hashmap 以降低时间复杂度
• 必须绝对——绝对——为一般情况提供时间复杂度
• 当 k=6, O(n^3) 时提示

她对时间复杂性比其他任何事情都更感兴趣。

有谁知道可以满足新约束的解决方案？

编辑：

假设，在正确的解决方案中，映射将存储输入的元素，然后映射用作查找表，就像k=2.

当子集的大小为 2（即k=2）时，答案很简单：循环并将所有元素加载到地图中。然后再次循环输入，这次在地图上搜索sum - input[i] where i is the index from 0 to n-1，这就是答案。据说这个微不足道的案例可以扩展到 where kis anything。

您将如何使用动态规划来查找数组中的正整数列表，其总和最接近但不等于某个正整数 K？

我对这个有点卡住了。

我和其他人一样一直在努力解决这个问题，我很确定已经有足够多的帖子来解释这个问题。然而，就完全理解它而言，我想分享我的想法，并从这里所有与子集和问题相关的伟大人物那里获得更有效的解决方案。

我在互联网上搜索过它，实际上有很多来源，但我真的很愿意重新实现一个算法或找到我自己的算法以便完全理解。

我正在努力解决的关键问题是考虑到集合大小会很大的效率。（我没有限制，只是在概念上很大）。我试图实现想法的两个阶段是找到两个等于给定整数T的数字，找到三个数字并最终找到K个数字。我有一些想法；

对于两个整数部分，我基本上对数组O(nlogn)进行排序，并为数组中的每个元素搜索其负值。（即如果数组元素是3搜索-3）。也许哈希表包含可能会更好，提供O(1)索引元素？

对于三个或更多整数，我发现了一篇很棒的博客文章；http://www.skorks.com/2011/02/algorithms-a-dropbox-challenge-and-dynamic-programming/。然而，即使是作者自己也表示它不适用于大量数据。

所以我对2和3 以及更多的整数有什么想法可以应用于子集问题。我正在努力建立一种对大输入也有效的动态编程方法。

我正在寻找多/多目标子集和问题的快速解决方案。

作为额外的限制（这使得 IMO 更容易计算），我们可以假设总和中包含的所有值都是正的，并且都绑定到一个已知的极限值。

我知道单目标子集和问题有一个 O(NK) 伪多项式解决方案，我已经实现了一个基于维基百科和这个堆栈交换答案的解决方案。

以其他方式解释这个问题，我有两组已知限制的正数。对于第一组中的每个值 A，第二组中的值的组合总和为 A。先验地知道第一组中的所有值具有对应的且不冲突的第二组中关联的值组合，是有一种已知的快速方法来计算第二组中的哪些元素与每个第一组值相关联？

给定一个N非负整数列表，提出一种算法来检查X列表中数字的总和是否等于剩余的N-X。

换句话说，涉及整个集合的子集和问题的更简单情况。

尝试的解决方案

按降序对列表的元素进行排序。将变量初始化SUM为第一个元素。删除第一个元素（最大，a(1)）。让a(n)表示n-th当前列表中的元素。

虽然 list 有多个元素，

1. 使SUM等于SUM + a(1)或SUM - a(1)，以最接近的为准a(2)。（其中最接近的均值|a(2) - SUM_POSSIBLE|是最小值）。

2. 删除a(1).

如果SUM等于-a(1)或a(1)，则存在线性和。

问题

我似乎无法解决上述算法，如果它是正确的，我想要一个证明。如果它是错误的（更有可能），有没有办法在线性时间内完成？

PS：如果我做错了什么，请原谅：S

我想找出一个算法来验证一个多重集是否是另一个多重集的子集和的并集，但是我自己挣扎了几个小时后失败了。

详情如下：

多重集 A：正整数集

Multiset B：一个正整数集（小于等于A，后面你会知道为什么）

算法功能：验证对于B中的所有数字，是否有一个数字或A中的数字之和可以匹配它们。A 中的每个数字只能使用一次，并且必须使用 A 中的所有数字。B 中的所有数字必须匹配。

一个澄清这一点的例子：假设 multiset A = {1, 3, 4, 4, 6} , B = {5, 6, 7}

那么算法会输出“TRUE”，因为5是1和4之和，6等于6，7是3和4之和。同时A中的所有数字都被使用且只使用一次，而A中的所有数字B 已检查。

但是对于A = {2, 6, 8}, B = {7, 9}，算法会输出“FALSE”，虽然2+6+8 = 7+9，但是B中没有一个数字是A中的数字之和.

一些注意事项：

1 已知条件，A中的数字之和等于B中的数字之和。

2 如示例所示，某个数字可以出现多次。

3 多重集中的每个数字只能使用一次，因此如果在一个解中使用 3（得到 7），则不能在另一个解中再次使用它。数字 4 出现了两次，因此它可以用于两种解决方案。

4 一个数字有多种解法是可能的，（比如 7 可以是 1 和 6，也可以是 3 和 4），但有些（比如 7 可以是 1 和 6）在验证过程中可能是错误的。

5 Multiset A 不大，最多30个元素

我尽力而为，但我的解决方案始终无法涵盖多集 A 和 B 的所有条件。我认为解决方案显然超出了我的范围。

所以，我真的需要你们聪明人的帮助。请帮我。任何答案将不胜感激！

（在您回复另一个 SO 问题的链接或将其作为副本关闭之前，请仔细阅读该问题。这与此问题的标准变体不同，我已经搜索了很长时间，所以我很确定没有这里不是这样的问题）

我需要找出最小可能的 S是否是X[i]的某个子集的总和> = T（某个目标值，小于完整集的总和）。

该集合不是很大（大约 40 个元素），但对于指数回溯解决方案来说仍然太大。

数字和总和很大（大约 10^15），所以动态编程不起作用（可能状态的数量很大，所以记忆表很快就会耗尽内存）。

出于同样的原因，Pisinger 的线性时间算法将不起作用（它是 O(nr)，其中 r 是总和的上限，在这种情况下太大了）。

是否有一些确定性算法可以在这种大和但很少数字的情况下帮助我？我不想求助于一些近似算法。

我需要了解这种递归是如何工作的，我了解简单的递归示例，但更高级的递归示例很难。甚至认为只有两行代码我遇到了问题……return语句本身。我只是对它的工作原理持空白，尤其是 and/or 运算符。任何见解都非常受欢迎。

How do I reset the value of blockIndex to its inital state when I call the method?

Say if I call it and pass in the value 4. I check if that value is greater than 9, if not I add the element at pos(0). But in tracing my function I see that it adds all the values of the vector. I just want it to add 1 element, then when it check if it is greater than 9, and it is not, revert it back to the initial value. How do I do this?

Possible Duplicate:
Subset Sum algorithm

I have a very easy problem which I can't figure out. I'm given an array of numbers and a value I need to get as close as possible to by making combinations of the sets. This algorithm has to be recursively. The result can't exceed the given number.

For example, given an array of {6, 9, 4, 2, 7} and I need to get as close as possible to 14. Then the result is 13 (by choosing the elements 9 and 4).

This is what I have so far:

A recursive function with 2 parameters: an index that gives information about the element you're about to add (or not) and the sum so far. For every element I make a binary decision: add it to the sumSoFar or not. I'm a bit confused about the base cases since the result can't exceed the number I have to get as close as possible to.

Could anyone help me with this?

Thanks in advance!