描述
给定一个仅包含数字 0
- 9
的字符串和一个目标值,返回在数字之间添加了 二元 运算符(不是一元)+
, -
或 *
之后所有能得到目标值的情况。
数字不包含前导 0
。
样例
样例 1:
- 输入:
- "123"
- 6
- 输出:
- ["1*2*3","1+2+3"]
样例 2:
- 输入:
- "232"
- 8
- 输出:
- ["2*3+2", "2+3*2"]
样例 3:
- 输入:
- "105"
- 5
- 输出:
- ["1*0+5","10-5"]
样例 4:
- 输入:
- "00"
- 0
- 输出:
- ["0+0", "0-0", "0*0"]
样例 5:
- 输入:
- "3456237490",
- 9191
- 输出:
- []
vector
vector
// write your code here
dfs(num, target, 0, "", 0, 0);
return result;
}
void dfs(string &num, int target, int start, string str, long long sum, long long lastF) {
if (num.size() == start) {
if (target == sum) {
result.push_back(str);
}
return;
}
long long x = 0;
string ret = "";
for (int i = start; i < num.size(); ++i) {
x = x * 10 + num[i] - '0'; //连续数据
ret += num[i];
if (start == 0) {
dfs(num, target, i + 1, str + ret, x, x);//第一次开始
}
else {
dfs(num, target, i + 1, str + "*" + ret, sum - lastF + x*lastF, x*lastF); //把上一个数据处理,和回溯
dfs(num, target, i + 1, str + "+" + ret, sum + x, x);
dfs(num, target, i + 1, str + "-" + ret, sum - x, -x);
}
if (x == 0) {
break;//去掉0开头
}
}
}