AcWing 4498. 指针 （DFS）

题目链接：4498. 指针 - AcWing题库

给定一个如下图所示的全圆量角器。

初始时，量角器上的指针指向刻度 00。

现在，请你对指针进行 nn 次拨动操作，每次操作给定一个拨动角度 aiai，由你将指针拨动 aiai 度，每次的拨动方向（顺时针或逆时针）由你自由决定。

请你判断，能否通过合理选择每次拨动的方向，使得指针最终仍然指向刻度 00。

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含一个整数 aiai，表示一次操作的拨动角度。

输出格式

如果可以做到指针最终仍然指向刻度 00，则输出 YES，否则输出 NO。

数据范围

前 44 个测试点满足 1≤n≤31≤n≤3。
所有测试点满足 1≤n≤151≤n≤15，1≤ai≤1801≤ai≤180。

输入样例1：

3
10
20
30

输出样例1：

YES

输入样例2：

3
10
10
10

输出样例2：

NO

输入样例3：

3
120
120
120

输出样例3：

YES

代码：

#include<bits/stdc++.h>   // 每次都有两种选择，则可以dfs暴搜
using namespace std;
#define endl "\n"

int n, a[20];
bool flag;

void dfs(int u, int s) {
    if(s == n) {
        if(u == 0) {
            if(!flag) {        // 没输出过就输出
                cout << "YES" << endl;  
                flag = true;   // 输出过就标记一下，只能输出一次
                return;
            }
        }
        return;
    }
    dfs((u + a[s] + 360) % 360, s + 1);  // 加上
    dfs((u - a[s] + 360) % 360, s + 1);  // 减去
}

int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);

    cin >> n;

    for(int i = 0; i < n; i ++) cin >> a[i];

    dfs(0, 0);

    if(!flag) cout << "NO" << endl;  // 没被标记过，则没输出过，即不可以

    return 0;
}