数组中与给定数相加的不同子序列

Question

在我为面试做准备的过程中，我遇到了一个问题，我很难找到最优的答案，

给我们一个数组A和一个整数Sum，我们需要找到和等于Sum的A的所有不同的子序列。

就像。A={1,2,3,5,6} Sum=6的答案应该是

{1,2,3}

{1,5}

{6}

现在我可以想到两种方法，

1. 使用递归(我认为这应该是面试问题的最后一件事)
2. 使用整数分区对Sum进行分区，并检查分区的元素是否存在于A中

请引导我的思想。

Answer 1

我同意杰森的观点。我想到了这个解决方案：

(如果将地图表示为数组，则复杂性为O(sum*|A|) )

• 调用输入集A和目标和sum
• 有一个元素B的映射，每个元素都是x:y，其中x (映射键)是和，y (映射值)是达到它的方法的数量。
• 首先，将0:1添加到映射中--有一种方法可以获得0(很明显，不使用任何元素)
• 对于A中的每个元素a，考虑B中的每个元素x:y。

- If `x+a` > `sum`, don't do anything.  
- If an element with the key `x+a` already exists in B, say that element is `x+a:z`, modify it to `x+a:y+z`.
- If an element with the key doesn't exist, simply add `x+a:y` to the set.

​

• 使用键sum查找元素，因此sum:x - x是我们想要的值。

如果B被排序(或数组)，您可以在“不要做任何事情”步骤中跳过B中的其余元素。

追溯它：

上面只给出计数，这将修改它给出实际的子序列。

在B中的每个元素，而不是和，存储所有的源元素和用于到达那里的元素(因此在B中的每个元素上都有一个对的列表)。

对于0:1，没有源元素。

对于x+a:y，源元素是x，要到达的元素是a。

在上述过程中，如果具有密钥的元素已经存在，则将这对x/a排队到元素x+a (enqueue是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}

Answer 2

这是子集和问题的一个变体。子集和问题询问是否存在与给定值相加的子集。您正在要求将所有的子集之和为给定的值。

子集和问题很难(更准确地说，它是NP-完全)，这意味着您的变体也很难(它不是NP-完全问题，因为它不是一个决策问题，但它是NP-硬问题)。

子集和问题的经典方法要么是递归，要么是动态规划。很明显，如何修改子集和问题的递归解决方案来回答您的变体。我建议您也看看子集和的动态规划解，看看是否可以为您的变体修改它(tbc:我不知道这是否真的可能)。无论是否可能，这肯定是一个非常有价值的学习练习，因为它肯定会提高您对动态编程的理解。

不过，如果你的问题的预期答案不是递归的解决方案，我会感到惊讶的。想出这个问题很容易，而且是一个可以接受的方法。要求动态规划的解决方案在飞行是有点太多的要求。

但是，您没有提到一个非常幼稚的方法来解决这个问题:生成所有子集，并对每个子集检查它是否与给定值相加。很明显这是指数式的，但它确实解决了这个问题。

Answer 3

我假设给定的数组包含不同的数字。让我们定义函数f(i，s) --这意味着我们在范围1，i中使用了一些数字，使用的数字之和是s。

让我们将所有值存储在二维矩阵中，即在单元格(i，j)中，我们将得到f(i，j)的值。现在，如果已经计算了位于上或左单元格的值，则可以计算f(i，s)的值，即f(i，s) =f(i-1，s)；(不取i索引数)和如果(s >= ai) f(i，s) += f(i-1，s- ai)。我们可以用自下而上的方法来填充所有矩阵，设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完全的，因此我们没有多项式算法，这种方法是最好的。