python - 列表与特定总和的组合

Question

我想用python解决这个问题:

Take the digits 1,2,3 up to 9 in numerical order and put either a plus sign or a minus sign or neither between the digits to make a sum that adds up to 100. For example, one way of achieving this is: 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100, which uses six plusses and minuses. What is the fewest number of plusses and minuses you need to do this?

我考虑从生成有效的元组开始，例如(1,2,34,567,89)，然后计算出哪些加起来等于 100，然后找出最短的。

为此，我首先创建了一个可能的数字、十位和百位的列表，因为我很确定没有 4 位数字的组合。

strnumbers = [str(x) for x in range(1,10)]
digits = [int(i) for i in strnumbers]
tens = [int(strnumbers[a] + strnumbers[a+1]) for a in range(8)]
hundreds = [int(strnumbers[a] + strnumbers[a+1] + strnumbers[a+2]) for a in range(7)]

但是，我不确定如何创建实际可能的列表。

我的问题有两个方面:

1. 您将如何使用十位和百位数字创建可能的元组？

2. 就计算而言，这是一种合理的方法吗？感觉我正在创造很多额外的工作

Answer 1

import itertools

results = []
for opers in itertools.product(('-','+',''),repeat=8):
    expression = '1{}2{}3{}4{}5{}6{}7{}8{}9'.format(*opers)
    result = eval(expression)
    if result == 100:
        results.append(expression)
best_result = min(results, key=len)
print(best_result, len(best_result)-9)