算法1:(暴力枚举) $O(n)$
//搜每个位置可以放什么,然后判断合法性,
#include <bits/stdc++.h>
using namespace std;
char op[10] = {' ', '+', '-'}; //按顺序存储可以使用的符号,搜索放那个符号
int n;
bool check(string s) {
int res = 0;
char op = ' ';
for (int i = 0; i < s.size(); ++ i) {
if (s[i] >= '1' && s[i] <= '9') {
int x = 0;
while (i < s.size() && s[i] != '+' && s[i] != '-') {
if (s[i] != ' ') x = x*10 + s[i] - '0';
i++;
}
if (op == ' ') res = x;
else if (op == '+') res += x;
else res -= x;
op = s[i];
}
}
return res == 0;
}
int cnt ;
void dfs(int u, string s) {
s = s + to_string(u); //把当前数字u拼接起来,n的后面不用放了,到达边界
if (u == n) {
if (check(s)) cout << s << endl;
// cout << s << endl;
return;
}
//枚举u后面的选择
for (int i = 0; i < 3; ++ i)
dfs(u + 1, s + op[i]);
}
int main() {
cin >> n;
dfs(1, "");//搜一下1的后面放什么符号
return 0;
}
算法2:() $O(n)$
//搜索所有方案,判断合法性,最多有3的8次方个方案 6561
//重心转移为怎么写,代码简洁,好些
#include <bits/stdc++.h>
using namespace std;
int n;
char op[5] = {' ', '+', '-'};
bool check(string s) {
s = '+' + s;//格式统一成 符号数字
int res = 0;
for (int i = 0; i < s.size(); ++ i) {
int j = i+1, x = 0; //下一个位置是数字, 开始的是符号
while (j < s.size() && s[j] != '+' && s[j] != '-') {
if (s[j] != ' ') x = x*10 + s[j] - '0';
j++;
}
if (s[i] == '+') res += x;
else res -= x;
i = j-1;
}
return res == 0;
}
void dfs(int u, string s) {
if (u == n+1) {
if (check(s)) cout << s << endl;
return;
}
//枚举u的后面可以选择的符号
for (int i = 0; i < 3; ++ i)
dfs(u+1, s + op[i] + to_string(u));
}
int main() {
cin >> n;
dfs(2, "1"); //搜一下有那些方式可以把2拼到已经拼好的表达式后
return 0;
}
bool check(string s) { //+1-2 3-4 5+6 7
s = '+' + s + '+';//格式统一成 符号数字 check函数怎么写简洁的问题
int res = 0, x = 0;
char per = '+';
for (int i = 1; i < s.size(); ++ i) {
if (s[i] == '+' || s[i] == '-') { //
if (per == '+') res += x;
else res -= x;
per = s[i];
x = 0;
} else {
if (s[i] != ' ') x = x*10 + s[i]-'0';
}
}
return res == 0;
}