5

在我目前的面试准备过程中，我遇到了一个难以获得最佳解决方案的问题，
给定一个数组A和一个整数Sum，我们需要找到A其和等于的所有不同子序列Sum。
例如。A={1,2,3,5,6} Sum=6那么答案应该是
{1,2,3}
{1,5}
{6}

目前我可以想到两种方法，

  1. 使用递归（我认为这应该是面试问题的最后一件事）
  2. 使用Integer Partitioning进行分区Sum，检查partition的元素是否存在于A

请指导我的想法。

4

3 回答 3

5

我同意杰森。想到了这个解决方案：（
复杂性是O(sum*|A|)如果您将地图表示为数组）

  • 调用输入集 A 和目标总和sum
  • 有一个元素 B 的映射，每个元素是x:y，其中x（映射键）是总和，y（映射值）是到达它的方式数。
  • 开始，添加0:1到地图 - 有 1 种方法可以达到 0（显然不使用元素）
  • 对于aA 中的每个元素，考虑x:yB中的每个元素。
    • 如果x+a> sum，什么也不做。
    • 如果x+aB 中已经存在具有键的元素，则说该元素是x+a:z，将其修改为x+a:y+z。
    • 如果带有键的元素不存在，只需添加x+a:y到集合中。
  • 使用 key 查找元素sum，因此sum:x-x是我们想要的值。

如果 B 已排序（或数组），您可以在“不做任何事情”步骤中简单地跳过 B 中的其余元素。

追溯它：

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

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

因为0:1没有源元素。

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

在上述过程中，如果有key的元素已经存在，则将pair入队x/a到该元素x+a（入队是一个O(1)操作）。

如果带有键的元素不存在，只需x/a在元素处创建一个包含一对的列表x+a。

要重建，只需从起点开始sum并递归地追溯您的方式。

我们必须小心重复序列（是吗？）和带有重复元素的序列。

示例 - 不追溯：

A={1,2,3,5,6}
总和=6

乙 =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}
总和=6

乙 =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: (not in{}表示实际元素，in{}表示映射条目)

{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}
于 2013-06-15T20:17:10.327 回答
0

我假设给定的数组包含不同的数字。让我们定义函数 f(i, s) - 这意味着我们使用了 [1, i] 范围内的一些数字，并且使用的数字之和为 s。

让我们将所有值存储在二维矩阵中，即在单元格 (i, j) 中，我们将获得 f(i, j) 的值。现在，如果已经计算了位于单元格 (i, s) 上方或左侧的单元格的值，我们可以计算 f(i, s) 的值，即 f(i, s) = f(i - 1, s);(不取 i 索引号）和 if(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 完全的，因此我们没有针对此问题的多项式算法，这种方法是最好的方法。

于 2013-06-15T21:06:32.413 回答
0

这是子集和问题的变体。子集和问题询问是否有一个子集对给定值求和。您要求总和为给定值的所有子集。

子集和问题很难（更准确地说，它是NP-Complete），这意味着您的变体也很难（它不是 NP-Complete，因为它不是决策问题，而是 NP-Hard）。

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

不过，如果您的问题的预期答案不是递归解决方案，那会让我感到惊讶。这很容易想出，并且是解决问题的可接受方法。即时要求动态编程解决方案有点多。

但是，您确实忽略了解决此问题的一种非常幼稚的方法：生成所有子集，并为每个子集检查其总和是否等于给定值。显然这是指数级的，但它确实解决了问题。

于 2013-06-15T16:25:56.617 回答