求和，以给定数中的阵列不同的子序列 [英] Distinct sub sequences summing to given number in an array

问题描述

在我目前的preparation面试，我遇到了一个问题，对此我有一些困难，以获得最佳的解决方案，
我们给出一个数组 A 和一个整数总和，我们需要找到<$ C $的所有不同的子序列C> A ，其总和等于总和。
对于如。 A = {1,2,3,5,6} 总和= 6 那么答案应该是
{1,2,3}
{1,5}
{6}

During my current preparation for interview, I encountered a question for which I am having some difficulty to get optimal solution,
We are given an array A and an integer Sum, we need to find all distinct sub sequences of A whose sum equals Sum.
For eg. A={1,2,3,5,6} Sum=6 then answer should be
{1,2,3}
{1,5}
{6}

presently我能想到这样做的两种方式，

Presently I can think of two ways of doing this,

1. 使用递归（我想应该是最后要考虑的一个面试问题）
2. 使用整数分割来划分总和并检查分区的内容是否为present在 A

1. Use Recursion ( which I suppose should be last thing to consider for an interview question)
2. Use Integer Partitioning to partition Sum and check whether the elements of partition are present in A

请指导我的想法。

推荐答案

我同意贾森。该解决方案浮现在脑海：
（复杂性是 O（总和* | A |）如果你重新present地图作为一个数组）

I agree with Jason. This solution comes to mind:
(complexity is O(sum*|A|) if you represent the map as an array)

• 调用输入集合A和目标总和之
• 有元素B中的地图，每一个元素是 X：Y ，其中 X （地图键）的总和与是（映射值）的方式来得到它的数量。
到
• 启动，添加 0：1 的地图 - 有1路才能到0（显然通过使用无元素）
• 对于每一个元素 A 在A，考虑每个元素 X：Y B中
  
  • 如果 X + A > 之，什么也不做。
  • 如果用钥匙元素X + A 已经存在于B，说这个元素是 X +一：Z ，修改为 X + A：Y + Z
  • 如果与键的元素不存在，只需添加 X + A：是来设定
  • Call the input set A and the target sum sum
  • Have a map of elements B, with each element being x:y, where x (the map key) is the sum and y (the map value) is the number of ways to get to it.
  • Starting of, add 0:1 to the map - there is 1 way to get to 0 (obviously by using no elements)
  • For each element a in A, consider each element x:y in B.
    
    • 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.

    如果B的排序（或数组），你可以简单地在什么也不做一步跳过B中的其他元素。

    If B is sorted (or an array), you can simply skip the rest of the elements in B during the "don't do anything" step.

    跟踪回：

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

    The above just gives the count, this will modify it to give the actual subsequences.

    目前在乙每个元素，来代替的总和，存储所有的源元件和用于到那里的元件（因此具有对在B各自元件清单）。

    At each element in B, instead of the sum, store all the source elements and the elements used to get there (so have a list of pairs at each element in B).

    有关 0：1 没有源元素

    有关 X +一：Y ，源元素是 X ，并获得该元素有 A 。

    For x+a:y, the source element is x and the element to get there is a.

    在上述过程中，如果与键的元素已经存在，排队的一对 X / A 的元素 X + A （排队是 O（1）操作）。

    During the above process, if an element with the key already exists, enqueue the pair x/a to the element x+a (enqueue is an O(1) operation).

    如果与键的元素不存在，只需创建一个对列表X / A 的元素 X +一个。

    If an element with the key doesn't exist, simply create a list with one pair x/a at the element x+a.

    要重建，只是开始之和递归地跟踪你回来的路。

    To reconstruct, simply start at sum and recursively trace your way back.

    我们必须小心重复序列（是吗？）和顺序在这里重复的元素。

    We have to be careful of duplicate sequences (do we?) and sequences with duplicate elements here.

    示例 - 不追查回来：

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

    A={1,2,3,5,6}
    sum = 6

    B = 0：1

    考虑 1
    添加 0 + 1
    B = 0：1,1：1

    Consider 1
    Add 0+1
    B = 0:1, 1:1

    考虑 2
    添加 0 + 2：1 ， 1 + 2：1
    B = 0：1,1：1,2：1,3：1

    Consider 2
    Add 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 < BR> B = 0：1，1：1,2：1,3：2,4：1,5：1，6：1

    Consider 3
    Add 0+3:1 (already exists -> add 1 to it), 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

    Consider 5
    B = 0:1, 1:1, 2:1, 3:2, 4:1, 5:2, 6:2
    Generated sums thrown away = 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

    Consider 6
    B = 0:1, 1:1, 2:1, 3:2, 4:1, 5:2, 6:3
    Generated sums thrown away = 7:1, 8:1, 9:2, 10:1, 11:2, 12:2

    然后，从 6：3 ，我们知道我们有3种方式去6

    Then, from 6:3, we know we have 3 ways to get to 6.

    示例 - 跟踪回：

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

    A={1,2,3,5,6}
    sum = 6

    B = 0：{}

    考虑 1
    B = 0：{} 1：{0/1}

    Consider 1
    B = 0:{}, 1:{0/1}

    考虑 2
    B = 0：{} 1：{} 0/1，2：{} 0/2，3：{1}

    Consider 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}

    Consider 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

    Consider 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} Generated sums thrown away = 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

    Consider 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} Generated sums thrown away = 7, 8, 9, 10, 11, 12

    然后，跟踪从 6 回：（而不是在 {} 指的是实际的元素，在 {} 表示一个映射项）

    Then, tracing back from 6: (not in {} means an actual element, in {} means a map entry)

    {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}
    

    这篇关于求和，以给定数中的阵列不同的子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！