Все-таки я предполагал, что это потребует больших усилий, когда писал комментарий.
opers = ['+', '-', '*']
def all_var(leafes):
global opers
if len(leafes) == 0:
return []
if len(leafes) == 1:
return [leafes]
res = []
for op in opers:
for i in range(len(leafes) - 1):
t = leafes[:i] + [f'({leafes[i]} {op} {leafes[i + 1]})'] + leafes[i + 2:]
res += all_var(t)
return res
s = '123456'
a = list(s)
n = 100
res = set([i[0] for i in all_var(a) if eval(i[0]) == n])
for i in res:
print(i)
Если обратиться к тем самым синтаксическим деревьям, о которых я упоминал в комментарии, то изначально мы имеем 6 листов: 1, 2, 3, 4, 5, 6
. Причем операция может быть произведена только между соседними листьями (очевидно, мы не можем сложить 1 и 3, никак не взаимодействуя с двойкой). Это дает возможность для данного набора листьев перебрать все возможные варианты постановки первого знака.
Далее по свойствам синтаксических деревьев, мы можем сказать, будто этих двух выбранных листьев никогда не существовало, а на их месте всегда был результат операции над ними:
1 2 3 4 5 6 -> 1 2 (3 + 4) 5 6 -> 1 2 7 5 6
.
Тогда мы получаем новый набор листьев, длина которого на 1 меньше, а значит мы можем использовать рекурсивную функцию перебора.
Разумеется, она очень тяжела по вычислительной сложности (для строки длины 7 уже выполняется секунд 9-10 на моем компьютере), однако она создает все возможные варианты расстановки знаков, насколько я могу судить.