Given a string that contains only digits `0-9` and a target value, return all possibilities to add binary operators (not unary) `+`, `-`, or `*` between the digits so they evaluate 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:

• `0 <= num.length <= 10`
• `num` only contain digits.

``````struct Solution;

impl Solution {
fn add_operators(num: String, target: i32) -> Vec<String> {
let mut res = vec![];
for i in 1..=num.len() {
let expr = &num[0..i];
let val = expr.parse::<i64>().unwrap();
if expr.len() > 1 && &expr[0..1] == "0" {
break;
}
Self::dfs(
i,
expr.to_string(),
val,
val,
'#',
&mut res,
&num,
target as i64,
);
}
res
}

fn dfs(
start: usize,
expr: String,
val: i64,
prev_val: i64,
prev_op: char,
all: &mut Vec<String>,
num: &str,
target: i64,
) {
if start == num.len() {
if val == target {
all.push(expr);
}
} else {
for end in start + 1..=num.len() {
let cur_expr = &num[start..end];
let cur_val = cur_expr.parse::<i64>().unwrap();
if cur_expr.len() > 1 && &cur_expr[0..1] == "0" {
break;
}
Self::dfs(
end,
format!("{}+{}", expr, cur_expr),
val + cur_val,
cur_val,
'+',
all,
num,
target,
);
Self::dfs(
end,
format!("{}-{}", expr, cur_expr),
val - cur_val,
cur_val,
'-',
all,
num,
target,
);
Self::dfs(
end,
format!("{}*{}", expr, cur_expr),
match prev_op {
'+' => val - prev_val + prev_val * cur_val,
'-' => val + prev_val - prev_val * cur_val,
_ => prev_val * cur_val,
},
prev_val * cur_val,
prev_op,
all,
num,
target,
)
}
}
}
}

#[test]
fn test() {
let num = "123".to_string();
let target = 6;
let mut res = vec_string!["1+2+3", "1*2*3"];
let mut ans = Solution::add_operators(num, target);
res.sort();
ans.sort();
assert_eq!(ans, res);
let num = "232".to_string();
let target = 8;
let mut res = vec_string!["2*3+2", "2+3*2"];
let mut ans = Solution::add_operators(num, target);
res.sort();
ans.sort();
assert_eq!(ans, res);
let num = "105".to_string();
let target = 5;
let mut res = vec_string!["1*0+5", "10-5"];
let mut ans = Solution::add_operators(num, target);
res.sort();
ans.sort();
assert_eq!(ans, res);
let num = "00".to_string();
let target = 0;
let mut res = vec_string!["0+0", "0-0", "0*0"];
let mut ans = Solution::add_operators(num, target);
res.sort();
ans.sort();
assert_eq!(ans, res);
let num = "3456237490".to_string();
let target = 9191;
let mut res = vec_string![];
let mut ans = Solution::add_operators(num, target);
res.sort();
ans.sort();
assert_eq!(ans, res);
}
``````