2020/4/8 招商银行第二道编程题——回溯法
先输入行数row，再输入row行“数字+目标”。问，如果在数字之间可以添上加减号，那么使得数字运算后等于目标的添法有几种？
如输入：
2
21 1
12345 3
输出：
1
1
回溯法可以解决。
坑的是，楼主没想到题目的意思是只能在数字之间加符号，而楼主提交的代码是考虑到第一个数字之前可能加负号的，遗憾没AC，考试结束自己改了一行代码，就没问题了。
下面是正确的代码，供大家参考下，水平有限，希望吧友指出我的不足。
#include<queue>
#include<vector>
#include<iostream>
#include<stdio.h>
#include<numeric>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<functional>
#include<iterator>
#include<sstream>
#include<string>
#include <math.h>
using namespace std;
void DFS(vector<int> nums, int loc, int value, int goal, int& count) {
if (loc == nums.size() && value == goal) {
++count;
return;
}
for (int i = 0; i < 2 && loc < nums.size(); ++i) {
if (i == 0) {
value += nums[loc];
DFS(nums, loc + 1, value, goal, count);
value -= nums[loc];
}
if (i == 1) {
value -= nums[loc];
DFS(nums, loc + 1, value, goal, count);
value += nums[loc];
}
}
}
int main() {
int row;
cin >> row;
vector<string> strs;
vector<int> goals;
string tmp;
getline(cin, tmp);
for (int i = 0; i < row; ++i) {
string str;
getline(cin, str);
stringstream ss(str);
string a, b;
ss >> a >> b;
strs.push_back(a);
goals.push_back(atoi(b.c_str()));
}
vector<vector<int> > figures;
for (auto str : strs) {
vector<int> a_row;
for (int i = 0; i < str.size(); ++i) {
a_row.push_back(str[i] - '0');
}
figures.push_back(a_row);
}
for (int i = 0; i < figures.size(); ++i) {
int count = 0;
vector<int> nums(figures[i].begin() + 1, figures[i].end());
DFS(nums, 0, figures[i][0], goals[i], count);
cout << count << endl;
}
return 0;
}
就算你真拿到牛友也会为你开心的