不同的子序列在数组中求和给定的数字
在我目前面试的准备期间，我遇到了一个问题，我很难获得最佳解决方案，
我们给出一个数组A和一个整数Sum ，我们需要找到的所有不同的子序列A ，其总和等于Sum 。
例如。 A={1,2,3,5,6} Sum=6那么答案应该是
{1,2,3}
{1,5}
{6}
目前我可以想到两种做法，
Sum进行分区并检查分区中的元素是否存在于A 请引导我的想法。
我同意杰森。 想到这个解决方案：
（如果将地图表示为数组，则复杂度为O(sum*|A|) ）
sum x:y ，其中x （地图键）是总和， y （地图值）是获取它的方式数。 0:1添加到地图 - 有1种方法可以达到0（显然，不使用任何元素） a ，考虑B中的每个元素x:y 。 x+a > sum ，不要做任何事情。 x+a元素，比如说该元素是x+a:z ，则将其修改为x+a:y+z 。 x+a:y添加到该集合。 sum查找元素，从而得出sum:x - x是我们期望的值。 如果B被排序（或者一个数组），你可以在“不要做任何事”步骤中简单地跳过B中其余的元素。
追溯：
以上只是给出了计数，这将修改它以给出实际的子序列。
在B中的每个元素中，而不是总和中，存储所有源元素和用于到达那里的元素（因此B中每个元素都有一个对列表）。
对于0:1 ，没有源元素。
对于x+a:y ，源元素是x并且要到达的元素是a 。
在上述过程中，如果具有该键的元素已经存在，则将该对x/a排入元素x+a （排队是O(1)操作）。
如果带键的元素不存在，只需在元素x+a处创建一个具有一对x/a的列表。
要重建，只需从sum开始并递归追溯你的方式。
我们必须小心重复序列（我们是否？），并在这里重复序列。
示例 - 不追溯：
A = {1,2,3,5,6}
sum = 6
B = 0:1
考虑1
加0+1
B = 0:1, 1:1
考虑2
添加0+2:1 1+2:1
B = 0:1, 1:1, 2:1, 3:1
考虑3
加0+3:1 （已经存在 - >加1 ）， 1+3:1 2+1:1 3+1:1
B = 0:1, 1:1, 2:1, 3:2, 4:1, 5:1, 6:1
考虑5
B = 0:1, 1:1, 2:1, 3:2, 4:1, 5:2, 6:2
产生的总和被扔掉= 7:1, 8:2, 9:1, 10:1, 11:1
考虑6
B = 0:1, 1:1, 2:1, 3:2, 4:1, 5:2, 6:3
产生的总和= 7:1, 8:1, 9:2, 10:1, 11:2, 12:2
然后，从6:3 ，我们知道我们有3种方法可以达到6。
示例 - 追溯：
A = {1,2,3,5,6}
sum = 6
B = 0:{}
考虑1
B = 0:{}, 1:{0/1}
考虑2
B = 0:{}, 1:{0/1}, 2:{0/2}, 3:{1/2}
考虑3
B = 0:{}, 1:{0/1}, 2:{0/2}, 3:{1/2,0/3}, 4:{1/3}, 5:{2/3}, 6:{3/3}
考虑5
B = 0:{}, 1:{0/1}, 2:{0/2}, 3:{1/2,0/3}, 4:{1/3}, 5:{2/3,0/5}, 6:{3/3,1/5}生成总和扔掉= 7, 8, 9, 10, 11
考虑6
B = 0:{}, 1:{0/1}, 2:{0/2}, 3:{1/2,0/3}, 4:{1/3}, 5:{2/3,0/5}, 6:{3/3,1/5,0/6}生成总和扔掉= 7, 8, 9, 10, 11, 12
然后，从6追溯：（不在{}表示实际元素，在{}表示地图条目）
{6}
{3}+3
{1}+2+3
{0}+1+2+3
1+2+3
Output {1,2,3}
{0}+3+3
3+3
Invalid - 3 is duplicate
{1}+5
{0}+1+5
1+5
Output {1,5}
{0}+6
6
Output {6}
这是子集和问题的一个变体。 子集和问题询问是否有一个子集合，以给出一个值。 你正在要求所有总和为给定值的子集。
sub-sum问题很难（更确切地说，它是NP-Complete），这意味着你的变体也很难（它不是NP-Complete，因为它不是一个决策问题，但它是NP-Hard）。
子集和问题的经典方法是递归或动态编程。 很显然，如何修改子集和问题的递归解决方案来回答您的变体。 我建议你也看看动态编程解决方案的子集总和，看看你是否可以修改你的变体（tbc：我不知道这是否可能）。 这无疑是一个非常有价值的学习练习，因为它无论如何都会增强您对动态编程的理解。
但是，如果对你的问题的预期答案只是递归解决方案，那将会让我感到惊讶。 这很容易想出来，并且是一个可接受的解决方法。 要求即时动态编程解决方案有点多问。
然而，你没有提及这个问题的一个非常天真的方法：生成所有的子集，并且为每个子集检查它是否与给定值相加。 显然这是指数，但它确实解决了这个问题。
我认为给定的数组包含不同的数字。 我们定义函数f（i，s） - 这意味着我们使用范围[1，i]中的一些数字，并且使用的数字总和为s。
我们将所有值存储在二维矩阵中，即在单元格（i，j）中，我们将有f（i，j）的值。 现在如果已经计算出位于单元（i，s）上方或下方的单元的值，我们可以计算f（i，s）的值，即f（i，s）= f（i-1，s）;如果（s> = a [i]）f（i，s）+ = f（i - 1，s - a [i]）， 我们可以用自下而上的方法来填充所有的矩阵，设置[f（0，0）= 1; f（0，i）= 0; 1 <= i <= s]，[f（i，0）= 1; 1 <= i <= n;]。 如果我们计算了所有的矩阵，那么我们在单元格f（n，S）中有答案; 因此，我们有总的时间复杂度O（n * s）和存储器复杂度O（n * s）;
如果我们注意到在每次迭代中我们只需要来自前一行的信息，那么我们可以提高内存复杂度，这意味着我们可以存储大小为2xS而非nxS的矩阵。 我们将存储器复杂度降低到线性为S.这个问题是NP完全的，因此我们没有多项式算法，这种方法是最好的。
链接地址: http://www.djcxy.com/p/39983.html上一篇: Distinct sub sequences summing to given number in an array