从数字字符串生成有效表达式以匹配目标数字

1. 引言

在本教程中，我们将探讨如何解决一个经典问题：在数字字符串的数字之间插入二元运算符（+、-、*），生成所有可能的表达式，使其计算结果等于给定的目标值。这个问题融合了字符串操作、递归和回溯技术，是面试中的高频题。

我们将采用回溯算法实现解决方案，深入分析其递归原理并验证功能。最后通过时间/空间复杂度分析确保算法效率。

2. 问题解析

先拆解问题核心：给定数字字符串和目标整数，需在数字间插入运算符（+、-、*）使表达式结果匹配目标值。关键约束包括：

✅ 输入限制：字符串长度1-10，目标值在32位整数范围内
✅ 数字规则：操作数不能有前导零（除非是"0"本身），如"05"无效但"0"有效
✅ 核心任务：探索所有操作数与运算符的组合，筛选出匹配目标值的表达式

例如：输入"123"和目标6，有效解为"1+2+3"和"123"。下面用回溯算法高效求解。

3. 回溯算法原理

回溯本质是系统化探索所有可能解的暴力优化技术。它通过递归构建部分解，并在违反约束时立即剪枝回溯，避免无效计算。

典型应用场景包括：

排列组合生成
数独/填字游戏求解
数学表达式求值
N皇后问题

本问题中，回溯将尝试所有可能的运算符插入位置，并动态计算表达式值。

4. 递归回溯实现

算法核心思路：递归尝试每个数字间的运算符插入，动态维护当前表达式和计算值，匹配目标时记录解。

4.1 表达式求值框架

入口方法process()初始化参数并启动递归：

List<String> process(String digits, int target) {
    final List<String> validExpressions = new ArrayList<>();
    evaluateExpressions(validExpressions, new Equation(digits, target), 0, new StringBuilder(), 0, 0);
    return validExpressions;
}

递归方法evaluateExpressions()处理两种状态：

终止状态：所有数字处理完毕时，检查结果是否匹配目标
探索状态：继续尝试后续数字组合

void evaluateExpressions(List<String> validExpressions, Equation equation,
  int index, StringBuilder currentExpression, long currentResult,
  long lastOperand) {

    if (allDigitsProcessed(equation.getDigits(), index)) {
        if (currentResult == equation.getTarget()) {
            validExpressions.add(currentExpression.toString());
        }
        return;
    }

    exploreExpressions(validExpressions, equation, index, currentExpression, currentResult, lastOperand);
}

4.2 算术运算处理

关键方法exploreExpressions()遍历所有可能的操作数组合：

void exploreExpressions(List<String> validExpressions, Equation equation,
  int index, StringBuilder currentExpression, long currentResult,
  long lastOperand) {

    for (int endIndex = index; endIndex < equation.getDigits().length(); endIndex++) {
        if (isWithLeadingZero(equation.getDigits(), index, endIndex)) {
            break; // 跳过无效前导零
        }

        long currentOperandValue = Long.parseLong(equation.getDigits()
          .substring(index, endIndex + 1));

        if (isFirstOperand(index)) {
            processFirstOperand(validExpressions, equation, endIndex, 
              currentExpression, currentOperandValue);
        } else {
            applyAddition(validExpressions, equation, endIndex, 
              currentExpression, currentResult, currentOperandValue);
            applySubtraction(validExpressions, equation, endIndex, 
              currentExpression, currentResult, currentOperandValue);
            applyMultiplication(validExpressions, equation, endIndex, 
              currentExpression, currentResult, currentOperandValue, lastOperand);
        }
    }
}

每种运算符的处理逻辑：

加法：直接累加操作数

void applyAddition(List<String> validExpressions, Equation equation,
int endIndex, StringBuilder currentExpression, long currentResult,
long currentOperandValue) {
  appendToExpression(currentExpression, Operator.ADDITION, currentOperandValue);
  evaluateExpressions(validExpressions, equation, endIndex + 1, currentExpression,
    currentResult + currentOperandValue, currentOperandValue);
  removeFromExpression(currentExpression, Operator.ADDITION, currentOperandValue); // 回溯
}

减法：直接减去操作数

void applySubtraction(List<String> validExpressions, Equation equation,
int endIndex, StringBuilder currentExpression, long currentResult,
long currentOperandValue) {
  appendToExpression(currentExpression, Operator.SUBTRACTION, currentOperandValue);
  evaluateExpressions(validExpressions, equation, endIndex + 1, currentExpression,
    currentResult - currentOperandValue, -currentOperandValue);
  removeFromExpression(currentExpression, Operator.SUBTRACTION, currentOperandValue);
}

乘法：特殊处理优先级（回溯修正前序操作）

void applyMultiplication(List<String> validExpressions, Equation equation,
int endIndex, StringBuilder currentExpression, long currentResult,
long currentOperandValue, long lastOperand) {
  appendToExpression(currentExpression, Operator.MULTIPLICATION, currentOperandValue);
  // 关键：撤销前序操作结果，应用乘法优先级
  evaluateExpressions(validExpressions, equation, endIndex + 1, currentExpression,
    currentResult - lastOperand + (lastOperand * currentOperandValue),
    lastOperand * currentOperandValue);
  removeFromExpression(currentExpression, Operator.MULTIPLICATION, currentOperandValue);
}

⚠️ 乘法优先级处理：通过currentResult - lastOperand + (lastOperand * currentOperandValue)修正计算顺序，确保乘法优先执行。

5. 实现测试

5.1 无效输入测试

验证无解情况返回空列表：

private static Stream<Arguments> equationsWithNoSolutions() {
    return Stream.of(Arguments.of("3456237490", 9191), Arguments.of("5", 0));
}

@ParameterizedTest
@MethodSource("equationsWithNoSolutions")
void givenEquationsWithNoSolutions_whenProcess_thenEmptyListIsReturned(String digits, int target) {
    final List<String> result = Backtracking.process(digits, target);
    assertTrue(result.isEmpty());
}

5.2 有效输入测试

验证典型用例的解集正确性：

Stream<Arguments> equationsWithValidSolutions() {
    return Stream.of(
        Arguments.of("1", 1, Collections.singletonList("1")), 
        Arguments.of("00", 0, Arrays.asList("0+0", "0-0", "0*0")),
        Arguments.of("123", 6, Arrays.asList("1+2+3", "1*2*3")), 
        Arguments.of("232", 8, Arrays.asList("2*3+2", "2+3*2")),
        Arguments.of("534", -7, Collections.singletonList("5-3*4")), 
        Arguments.of("1010", 20, Collections.singletonList("10+10")),
        Arguments.of("1234", 10, Arrays.asList("1+2+3+4", "1*2*3+4")), 
        Arguments.of("1234", -10, Collections.singletonList("1*2-3*4")),
        Arguments.of("12345", 15, Arrays.asList("1+2+3+4+5", "1*2*3+4+5", "1-2*3+4*5", "1+23-4-5"))
    );
}

@ParameterizedTest
@MethodSource("equationsWithValidSolutions")
void givenEquationsWithValidSolutions_whenProcess_thenValidResultsAreReturned(
  String digits, int target, List<String> expectedSolutions) {
    List<String> result = Backtracking.process(digits, target);
    assertEquals(expectedSolutions.size(), result.size());
    expectedSolutions.stream()
      .map(result::contains)
      .forEach(Assertions::assertTrue);
}

测试要点：

验证解的数量匹配
确保所有预期解均被包含

6. 复杂度分析

时间复杂度

组合爆炸：n个数字有n-1个间隔，每个间隔有4种选择（+、-、*、无操作符）
总组合数：O(4^(n-1))
单次操作：表达式构建和求值O(n)
总时间：O(4^(n-1) * n)

空间复杂度

递归栈：深度O(n)
结果存储：最多O(4^(n-1))个解，每个解长度O(n)
总空间：O(n + 4^(n-1) * n)

⚠️ 实际注意：当n>10时，组合数爆炸，需考虑剪枝优化。

7. 总结

本文通过回溯算法实现了数字字符串表达式生成问题，核心在于：

递归探索所有运算符组合
动态维护表达式和计算值
特殊处理乘法优先级
严格校验前导零等约束

完整代码见GitHub仓库。此算法可扩展至更复杂的表达式生成场景，是解决组合问题的经典范式。

Persistence

REST

Security