如果可以通过在列表中放置加法或减法运算来获取目标整数，则应返回 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")

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

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

Answer 2

代码问题：

• 当你说f(5, [5, 2]) = false. There's no way to add or subtract 5 and 2 to get 5..但是有。如何：magic_number - numbers[0] == 0.这正是正在发生的事情，因为您在代码中编写了util(numbers, i + 1, magic_number)。忽略第 i 个元素 (magic_number[i](，它既不加也不减，同时将i增加 1。

因此，我假设您想在添加或减去时考虑数组中的所有元素。

• 此外，当您执行return 1 if (magic_number == 0)时，您不会检查是否遍历了整个列表。

所以恕我直言，你可以做这样的事情：

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 == n and magic_number != 0:
return 0
if magic_number == 0 and i == n:
return 1
return 1 if 1 in (util(numbers, i + 1, magic_number - numbers[i]), util(numbers, i + 1, magic_number + numbers[i])) else 0

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

# True
# False

Answer 3

这是一种子集和问题。

这可以通过动态规划来解决。

为了使数据适合子集和公式，可以列出源数据以及否定的数据元素，并提供检查对 (x，-x( 中只有一个元素参与和形成(例如，使用二进制掩码(。

+最小使用元素数的限制 = 2