基于itertools的数字拼接求和问题：示例3失效的排查与解决

问题背景 #

需求是：将连续数字序列12345678910111213…N的部分字符间隙添加+号，使所有项的总和等于给定值M，输入两个正整数N和M，输出有效表达式示例。当前输入N=15，M=1117614时，原代码无法生成有效表达式。

原代码问题分析 #

原代码核心逻辑完全误解了题目要求：

• 原代码将1到N的每个完整数字（如10作为"10"）作为独立元素，仅在这些完整数字之间选择添加+或拼接，只能实现完整数字的合并，无法对单个数字（如10拆成"1"和"0"）进行拆分。
• 而题目要求基于原始连续字符序列的任意拆分，比如序列到10是12345678910，允许拆分为12+3+45+6789+1+0这种跨完整数字的形式。

修复后的代码 #

正确思路是先生成完整的数字字符序列，再遍历所有字符间隙的拆分可能（每个间隙可选加+或拼接），计算拆分后的总和是否匹配M：

def find_expression(n, m):
    # 生成完整的连续数字字符串
    full_num_str = ''.join(str(i) for i in range(1, n+1))
    str_length = len(full_num_str)
    
    # 遍历所有拆分可能：用二进制位标记每个间隙是否加+（1=加+，0=拼接）
    for mask in range(1 << (str_length - 1)):
        current_segment = full_num_str[0]
        expression_parts = []
        
        for i in range(1, str_length):
            # 检查当前间隙是否需要加+
            if mask & (1 << (i - 1)):
                expression_parts.append(current_segment)
                current_segment = full_num_str[i]
            else:
                current_segment += full_num_str[i]
        # 添加最后一段数字
        expression_parts.append(current_segment)
        
        # 计算总和（允许前导零，符合示例要求）
        total = sum(int(seg) for seg in expression_parts)
        if total == m:
            return '+'.join(expression_parts)
    
    return None

# 测试用例
print(find_expression(5, 15))  # 输出: 1+2+3+4+5
print(find_expression(4, 46))  # 输出: 12+34
result = find_expression(15, 1117614)
print(result + '=' + str(1117614) if result else 'No valid expression found.')

效果说明 #

修复后的代码会遍历所有可能的字符拆分方式，包括跨完整数字的拆分，能够正确找到输入N=15，M=1117614对应的有效表达式。

内容的提问来源于stack exchange，提问作者Григорий Шабалкин