leetcode

0 class Solution {

1 vector<string> res;

2

3 vector<long long> operan;

4 vector<char> operat;

5

6 void rec(long long target, const string &num, int start, long long total, long long prev) {

7 if (start == size(num)) {

8 if (total != target) return;

9

10 res.push_back(to_string(operan[0]));

11 for (int i = 0; i < size(operat); i++) {

12 res.back() += operat[i] + to_string(operan[i + 1]);

13 }

14

15 return;

16 }

17

18 operan.push_back(-1);

19 operat.push_back('_');

20 for (long long i = start, crnt = 0; i < size(num); i++) {

21 operan.back() = crnt = crnt * 10 + num[i] - '0';

22

23 operat.back() = '+';

24 rec(target, num, i + 1, total + crnt, crnt);

25

26 operat.back() = '-';

27 rec(target, num, i + 1, total - crnt, -crnt);

28

29 operat.back() = '*';

30 rec(target, num, i + 1, total + prev * (crnt - 1), prev * crnt);

31

32 if (num[start] == '0') break;

33 }

34 operan.pop_back();

35 operat.pop_back();

36 }

37

38 public:

39 vector<string> addOperators(const string &num, int target) {

40

41 operan.push_back(-1);

42 for (long long i = 0, crnt = 0; i < size(num); i++) {

43 operan.back() = crnt = crnt * 10 + num[i] - '0';

44 rec(target, num, i + 1, crnt, crnt);

45

46 if (num[0] == '0') break;

47 }

48

49 return res;

50 }

51 };