python - 如果可以通过在列表中放置加法或减法运算来获得目标整数，则编写应返回 true 的函数

Question

例子 ：

f(5, [5, 2]) = false. There's no way to add or subtract 5 and 2 to get 5.

f(13, [3, 9, 3, 2]) = true. 3 + 9 + 3 - 2 = 13.

f(0, []) = true

f(1, []) = false

我尝试了下面的代码，但在某些时候，它仍然崩溃了。你们有什么简单或有效的解决方案吗？

def getWays(magic_number, numbers):
    if( util(numbers, 0, magic_number) > 0 ):
        return True

    return False

def util(numbers, i, magic_number):

    n = len(numbers)

    if( i >= len(numbers) and magic_number != 0 ):
        return 0

    if (magic_number == 0):
        return 1

    return util(numbers, i + 1, magic_number) + util(numbers, i + 1, magic_number - numbers[i]) + util(numbers, i + 1, magic_number + numbers[i])

if(getWays(13, [3, 9, 3, 2])):
    print("True")
else:
    print("False")

注意：这不是任何家庭作业或作业。我只是为了练习而尝试。

标签： pythonalgorithm

Answer 1

您可以使用以下递归函数：

from operator import add, sub
def getWays(target, operands):
    if not operands:
        return target == 0
    *remaining, operand = operands
    return any(getWays(operator(target, operand), remaining) for operator in (add, sub))

以便：

print(getWays(5, [5, 2]))
print(getWays(13, [3, 9, 3, 2]))
print(getWays(0, []))
print(getWays(1, []))

会输出：

False
True
True
False