Today I have done leetcode's September LeetCoding Challenge with cpp.

September LeetCoding Challenge 18

Description

Expression Add Operators

Given a string num that contains only digits and an integer target, return all possibilities to add the binary operators '+', '-', or '*' between the digits of num so that the resultant expression evaluates to the target value.

Example 1:

Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]

Example 2:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]

Example 3:

Input: num = "105", target = 5
Output: ["1*0+5","10-5"]

Example 4:

Input: num = "00", target = 0
Output: ["0*0","0+0","0-0"]

Example 5:

Input: num = "3456237490", target = 9191
Output: []

Constraints:

• 1 <= num.length <= 10
• num consists of only digits.
• -231 <= target <= 231 - 1

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
  vector<string> answer;
  void solve(string &num, int target, int start, string expr, long value, long last) {
    if(start == num.length()) {
      if(target == value) {
        answer.push_back(expr);
      }
      return;
    }

    long n = 0;
    string nStr;
    for(int i = start; i < num.length(); ++i) {
      n *= 10;
      n += num[i] - '0';
      nStr.push_back(num[i]);

      if(!start) {
        solve(num, target, i + 1, nStr, n, n);
      } else {
        solve(num, target, i + 1, expr + "*" + nStr, value - last + n * last, n * last);
        solve(num, target, i + 1, expr + "+" + nStr, value + n, n);
        solve(num, target, i + 1, expr + "-" + nStr, value - n, -n);
      }

      if(n == 0) break;
    }
  }
public:
  vector<string> addOperators(string num, int target) {
    solve(num, target, 0, "", 0, 0);
    return answer;
  }
};

// Accepted
// 20/20 cases passed (415 ms)
// Your runtime beats 49.31 % of cpp submissions
// Your memory usage beats 12.67 % of cpp submissions (95.2 MB)