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

Question

在我目前的面试准备期间,我遇到了一个问题,我遇到了一些难以获得最优解的问题.
我们给出了一个数组A和一个整数Sum,我们需要找到所有不同的子序列,A其总和等于Sum.
例如.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(显然不使用任何元素)
• 对于aA中的每个元素,请考虑x:yB中的每个元素.
  
  • 如果x+a> sum,请不要做任何事情.
  • 如果x+aB中已存在具有键的元素,则表示该元素为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(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}