子集和两套和目标

Question

我有点困惑在这里解决这个计算。我设法使用python创建子集合程序。下面是代码：

def subsetsum(array,num): 

    if num == 0 or num < 1: 
     return None 
    elif len(array) == 0: 
     return None 
    else: 
     if array[0] == num: 
      return [array[0]] 
     else: 
      with_v = subsetsum(array[1:],(num - array[0])) 
      if with_v: 
       return [array[0]] + with_v 
      else: 
       return subsetsum(array[1:],num) 

我的问题是，如果我有两套阵列即数组1 = [4,5,1,7,2,1]和数组2 = [7,1,4， 6,3,2]，其中目标是18的方式数组1应该有一个目标8和数组2目标为10。

而且如果我有一个有错误的更大的余量阵列。我将如何减少它？

Answer 1

按照你的榜样，arr1=[4,5,1,7,2,1]，arr2=[7,1,4,6,3,2]和target=18，您可以使用一组保存的每个元素之间arr1和目标下一个迭代arr2的差异，并检查该元素在集合，如果是这样的话，那么你已经找到arr1中的一个数字和arr2中的一个数字，它们的总和等于目标。

def getSubsetSum(arr1, arr2, target): 
    diffs = set() 
    for a in arr1: 
     diffs.add(target - a) 
    for b in arr2: 
     if b in diffs: 
      return (target -b, b) 
    return None