子集和问题的实现给出了错误的答案

Question

我想为子集和问题实现一个解决方案。但在下面的实现中，所有测试用例都返回 'No'。有人可以指出代码中的问题吗？

def isSubls(l, n, s):

    if s == 0:
        return 'Yes'
    if n == 0 and s != 0:
        return False
    if l[n - 1] > s:
        return isSubls(l, n - 1, s)

    return isSubls(l, n-1, s) or isSubls(l, n-1, s-l[n-1])


def run():

    for _ in range(int(input())):

        n, m = map(int, input().split())
        l = []

        for i in range(n):
            l.append(int(input()))

        print(isSubls(l, n, m))


run()

Answer 1

方法isSubls()完全正确。

我测试了你的代码如下：

def isSubls(l,n, s) : 
    if (s == 0) : 
        return True
    if (n == 0 and s != 0) : 
        return False 
    if (l[n - 1] > s) : 
        return isSubls(l, n - 1, s); 
    return isSubls(l, n-1, s) or isSubls(l, n-1, s-l[n-1]) 


set = [3, 34, 4, 12, 5, 2] 
sum = 9
n = len(set) 
if (isSubls(set, n, sum) == True) : 
    print("Found a subset with given sum") 
else : 
    print("No subset with given sum")

判决：

子集和问题的实现给出了错误的答案

Implementation of subset sum problem is giving wrong answer

python

algorithm

subset

subset-sum

data-structures