Python算法实现：在1到N的数字间添加+使结果为M

思路拆解 #

简单说就是，数字串里每两个相邻数字之间，要么插加号，要么不插（把俩数字合并成一个数）。我们可以挨个试所有可能的分割组合，算每种组合的总和，找到总和等于M的那个组合就行。

代码实现（Python） #

def find_target_expression(n, target):
    # 先把1到N拼成连续的字符串，比如n=5就是"12345"
    num_str = ''.join(str(i) for i in range(1, n+1))
    valid_expressions = []

    def try_split(pos, current_total, expr_parts):
        # pos：当前处理到字符串的第pos个字符
        # current_total：当前已经加出来的总和
        # expr_parts：存当前表达式的各个部分，比如["12", "34"]
        if pos == len(num_str):
            # 处理完所有字符了，检查总和对不对
            if current_total == target:
                # 把 parts 拼成完整表达式
                full_expr = '+'.join(expr_parts) + f'={target}'
                valid_expressions.append(full_expr)
            return
        
        # 从当前位置开始，尝试截取1位、2位...直到末尾的数字
        for i in range(pos, len(num_str)):
            current_num_str = num_str[pos:i+1]
            current_num = int(current_num_str)
            if pos == 0:
                # 第一个数字，直接初始化
                try_split(i+1, current_num, [current_num_str])
            else:
                # 不是第一个，就把当前数字加到总和里，更新表达式片段
                try_split(i+1, current_total + current_num, expr_parts + [current_num_str])
    
    try_split(0, 0, [])
    # 返回第一个找到的有效表达式，没找到就返回"无解"
    return valid_expressions[0] if valid_expressions else "无解"

# 测试示例
print(find_target_expression(5, 15))  # 输出：1+2+3+4+5=15
print(find_target_expression(4, 46))  # 输出：12+34=46

代码说明 #

1. 生成数字串：把1到N的数字挨个拼起来，变成一个连续的字符串，方便后续分割。
2. 尝试所有分割方式：用递归的方式，从字符串的第一个字符开始，每次尝试截取1位、2位……直到末尾的数字，要么单独作为一项，要么和前面的合并（其实就是不插加号的情况，通过截取更长的子串实现）。
3. 检查结果：当把整个字符串处理完时，看看当前的总和是不是等于目标M，如果是，就把当前的表达式片段拼成完整的式子存起来。
4. 返回结果：找到第一个符合要求的表达式就返回，要是没有就返回“无解”。

额外提示 #

• 如果某个N和M存在多种分割方式（比如可能有多个表达式都能得到M），你可以把valid_expressions[0]改成valid_expressions，这样就能返回所有解。
• 要是输入的M太大或者太小，根本不可能通过分割得到，代码就会返回“无解”。

内容的提问来源于stack exchange，提问作者PUser