时间戳

首页 > 解决方案 > 返回子集和问题中的数组元素

python - 返回子集和问题中的数组元素

问题描述

对于以下子集和问题的递归解决方案（请参阅此链接），如果存在a其和等于值的任何子集，则以下代码返回 truesum 

def isSubsetSum(set,n, sum) : 

    # Base Cases 
    if (sum == 0) : 
        return True
    if (n == 0 and sum != 0) : 
        return False

    # If last element is greater than sum, then ignore it 
    if (set[n - 1] > sum) : 
        return isSubsetSum(set, n - 1, sum); 

    # else, check if sum can be obtained by any of the following 
    # (a) including the last element 
    # (b) excluding the last element    
    return isSubsetSum(set, n-1, sum) or isSubsetSum(set, n-1, sum-set[n-1]) 

set = [2, 1, 14, 12, 15, 2] 
sum = 9
n = len(set) 
if (isSubsetSum(set, n, sum) == True) : 
    print("Found a subset with given sum") 
else : 
    print("No subset with given sum")

我怎样才能返回a满足的索引sum？

另外，如何使该函数适用于 array 中的负整数a。

标签： pythonnumpydynamic-programming

解决方案

这是一种可能性：

def isSubsetSum(numbers, n, x, indices):
    # Base Cases
    if (x == 0):
        return True
    if (n == 0 and x != 0):
        return False
    # If last element is greater than x, then ignore it
    if (numbers[n - 1] > x):
        return isSubsetSum(numbers, n - 1, x, indices)
    # else, check if x can be obtained by any of the following
    # (a) including the last element
    found = isSubsetSum(numbers, n - 1, x, indices)
    if found: return True
    # (b) excluding the last element
    indices.insert(0, n - 1)
    found = isSubsetSum(numbers, n - 1, x - numbers[n - 1], indices)
    if not found: indices.pop(0)
    return found

numbers = [2, 1, 4, 12, 15, 3]
x = 9
n = len(numbers)
indices = []
found = isSubsetSum(numbers, n, x, indices)
print(found)
# True
print(indices)
# [0, 2, 5]

编辑：为了更简洁的界面，您可以将前一个函数包装在另一个函数中，该函数返回成功时的索引列表，None否则：

def isSubsetSum(numbers, x):
    indices = []
    found = _isSubsetSum_rec(numbers, len(numbers), x, indices)
    return indices if found else None

def _isSubsetSum_rec(numbers, n, x, indices):
    # Previous function

推荐阅读