Plus Equation

#include <bits/stdc++.h>

using namespace std;

string answer = "";
string s;
int target;

void backtracking(int index, string &curAns, int curNum, int curSum) {
  if (!answer.empty())
    return;
  if (index == s.size()) {
    curSum += curNum;
    if (curSum == target) {
      answer = curAns;
    }
    return;
  }
  // Đặt dấu + trước vị trí hiện tại
  if (index) {
    string newAns = curAns + "+" + s[index];
    int newNum = s[index] - '0';
    int newSum = curSum + curNum;
    backtracking(index + 1, newAns, newNum, newSum);
  }
  string newAns = curAns + s[index];
  int newNum = curNum * 10 + s[index] - '0';
  int newSum = curSum;
  // Không đặt dấu +
  backtracking(index + 1, newAns, newNum, newSum);

}

void backtrack(int index, string &curAns, int curSum) {
  if (!answer.empty())
    return;
  if (index == s.size()) {
    if (curSum == target) {
      answer = curAns;
    }
    return;
  }
  // | 154+89001
  string newAns = curAns;
  if (index != 0) newAns += "+";
  newAns += s[index];
  int curNum = s[index] - '0';
  for (int i = index + 1; i <= s.size(); i++) {
    backtrack(i, newAns, curSum + curNum);
    curNum = curNum * 10 + s[i] - '0';
    newAns += s[i];
  }
  backtrack(s.size(), newAns, curSum + curNum);
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    cin >> s >> target;
    string curAns = "";
    answer = "";
    // backtracking(0, curAns, 0, 0);
    backtrack(0, curAns, 0);
    cout << answer << endl;
  }
}