Skip to content

282. Expression Add Operators 👍

  • Time: $O(n4^{n - 1})$
  • Space: $O(n^2)$
 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
44
45
46
47
48
49
class Solution {
 public:
  vector<string> addOperators(string num, int target) {
    vector<string> ans;
    dfs(num, target, 0, 0, 0, {}, ans);
    return ans;
  }

 private:
  string join(const vector<string>& path) {
    string joined;
    for (const string& s : path)
      joined += s;
    return joined;
  }

  void dfs(const string& num, int target, int start, long prev, long eval,
           vector<string>&& path, vector<string>& ans) {
    if (start == num.length()) {
      if (eval == target)
        ans.push_back(join(path));
      return;
    }

    for (int i = start; i < num.length(); ++i) {
      if (i > start && num[start] == '0')
        return;
      const string& s = num.substr(start, i - start + 1);
      const long curr = stol(s);
      if (start == 0) {
        path.push_back(s);
        dfs(num, target, i + 1, curr, curr, std::move(path), ans);
        path.pop_back();
      } else {
        for (const string& op : {"+", "-", "*"}) {
          path.push_back(op + s);
          if (op == "+")
            dfs(num, target, i + 1, curr, eval + curr, std::move(path), ans);
          else if (op == "-")
            dfs(num, target, i + 1, -curr, eval - curr, std::move(path), ans);
          else
            dfs(num, target, i + 1, prev * curr, eval - prev + prev * curr,
                std::move(path), ans);
          path.pop_back();
        }
      }
    }
  }
};

 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
class Solution {
  public List<String> addOperators(String num, int target) {
    List<String> ans = new ArrayList<>();
    dfs(num, target, 0, 0, 0, new StringBuilder(), ans);
    return ans;
  }

  private void dfs(String num, int target, int s, long prev, long eval, StringBuilder sb,
                   List<String> ans) {
    if (s == num.length()) {
      if (eval == target)
        ans.add(sb.toString());
      return;
    }

    for (int i = s; i < num.length(); ++i) {
      if (i > s && num.charAt(s) == '0')
        return;
      final long curr = Long.parseLong(num.substring(s, i + 1));
      final int length = sb.length();
      if (s == 0) { // the first number
        dfs(num, target, i + 1, curr, curr, sb.append(curr), ans);
        sb.setLength(length);
      } else {
        dfs(num, target, i + 1, curr, eval + curr, sb.append("+").append(curr), ans);
        sb.setLength(length);
        dfs(num, target, i + 1, -curr, eval - curr, sb.append("-").append(curr), ans);
        sb.setLength(length);
        dfs(num, target, i + 1, prev * curr, eval - prev + prev * curr, sb.append("*").append(curr),
            ans);
        sb.setLength(length);
      }
    }
  }
}

 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
class Solution:
  def addOperators(self, num: str, target: int) -> list[str]:
    ans = []

    def dfs(start: int, prev: int, eval: int, path: list[str]) -> None:
      if start == len(num):
        if eval == target:
          ans.append(''.join(path))
        return

      for i in range(start, len(num)):
        if i > start and num[start] == '0':
          return
        s = num[start:i + 1]
        curr = int(s)
        if start == 0:
          path.append(s)
          dfs(i + 1, curr, curr, path)
          path.pop()
        else:
          for op in ['+', '-', '*']:
            path.append(op + s)
            if op == '+':
              dfs(i + 1, curr, eval + curr, path)
            elif op == '-':
              dfs(i + 1, -curr, eval - curr, path)
            else:
              dfs(i + 1, prev * curr, eval - prev + prev * curr, path)
            path.pop()

    dfs(0, 0, 0, [])
    return ans