AcWing 1370. 零和序列(简单DFS)
原题链接
简单
作者:
Vason
,
2024-04-18 22:19:10
,
所有人可见
,
阅读 2
DFS枚举所有情况后,检查结果是否符合总和为0
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10;
int n;
char c[4] = {' ', '+', '-'};
char path[N];
void dfs(int u)
{
if(u >= n)
{
int s = 0, t = 1;
for(int i = 1; i < n; i ++)
{
if(path[i] != ' ')
{
s += t;
if(path[i] == '+') t = i + 1;
else t = -(i + 1);
}
else
{
if(t > 0) t = t * 10 + (i + 1);
else t = t * 10 - (i + 1);
}
}
s += t;
if(s == 0)
{
for(int i = 1; i < n; i ++)
cout << i << path[i];
cout << n << endl;
}
return;
}
for(int i = 0; i < 3; i ++)
{
path[u] = c[i]; // 每次循环会更新该位置上的符号,不用写状态还原
dfs(u + 1);
}
}
int main()
{
cin >> n;
dfs(1);
return 0;
}