友情支持

如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜

支付宝

微信

有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

282. 给表达式添加运算符

给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target,在 num 的数字之间添加 二元 运算符(不是一元)+- ,返回 *所有 能够得到 target 的表达式。

注意,返回表达式中的操作数 不应该 包含前导零。

示例 1:

输入: num = "123", target = 6
输出: ["123", "1*2*3"]
解释: “1*2*3” 和 “123” 的值都是6。

示例 2:

输入: num = "232", target = 8
输出: ["2*3+2", "2+3*2"]
解释: “2*3+2” 和 “2+3*2” 的值都是8。

示例 3:

输入: num = "3456237490", target = 9191
输出: []
解释: 表达式 “3456237490” 无法得到 9191 。

提示:

  • 1 <= num.length <= 10

  • num 仅含数字

  • -231 <= target <= 231 - 1

思路分析

回溯!

回溯就是对两个变量做遍历来:

  1. 根据不同长度,把数字切分成更小的数字。但是,不能有以 0 开头的数字。

  2. 三种运算符。

0282 10
  • 一刷

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-07-07 20:46:03
 */
public List<String> addOperators(String num, int target) {
  List<String> result = new ArrayList<>();
  backtrack(num, target, result, new StringBuilder(), 0, 0, 0);
  return result;
}

private void backtrack(String num, int target, List<String> result,
                       StringBuilder path, int start, long eval, long pre) {
  if (start == num.length()) {
    if (target == eval) {
      result.add(path.toString());
    }
    return;
  }
  for (int i = start; i < num.length(); i++) {
    // 数字不能以 0 开头
    if (num.charAt(start) == '0' && i > start) {
      break;
    }
    long cur = Long.parseLong(num.substring(start, i + 1));
    int len = path.length();
    if (start == 0) {
      backtrack(num, target, result, path.append(cur), i + 1, cur, cur);
      // 通过设置长度来实现回溯
      path.setLength(len);
    } else {
      backtrack(num, target, result, path.append("+").append(cur), i + 1, eval + cur, cur);
      path.setLength(len);

      backtrack(num, target, result, path.append("-").append(cur), i + 1, eval - cur, -cur);
      path.setLength(len);

      backtrack(num, target, result, path.append("*").append(cur), i + 1,
        eval - pre + pre * cur, pre * cur);
      path.setLength(len);
    }
  }
}