AcWing 1370. 零和序列
原题链接
简单
作者:
三鹤亥一
,
2025-04-01 15:48:58
· 山东
,
所有人可见
,
阅读 1
n = int(input())
def check(expr):
# 合并空格
s = expr.replace(' ', '')
# 分割数字和运算符
tokens = []
i = 0
while i < len(s):
if s[i] in '+-':
tokens.append(s[i])
i += 1
else:
num = ''
while i < len(s) and s[i].isdigit():
num += s[i]
i += 1
tokens.append(int(num))
# 计算表达式
res = tokens[0]
i = 1
while i < len(tokens):
op = tokens[i]
num = tokens[i + 1]
if op == '+':
res += num
else:
res -= num
i += 2
return res == 0
def dfs(u, expr):
if u == n:
if check(expr):
print(expr)
return
# 尝试插入空格
dfs(u + 1, expr + ' ' + str(u + 1))
# 尝试插入 '+'
dfs(u + 1, expr + '+' + str(u + 1))
# 尝试插入 '-'
dfs(u + 1, expr + '-' + str(u + 1))
# 从数字1开始,初始表达式为"1"
dfs(1, "1")