1601 添加运算符 枚举 递归dfs

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+10, inf = 0x3f3f3f3f;
int a[N], vis[N];
int n, ans;

// 计算函数：根据运算符i对sum和a[x]进行运算
int cal(int sum, int i, int x) {
    if(i == 1) return sum + a[x]; // 加法
    if(i == 2) return sum - a[x]; // 减法
    if(i == 3) return sum * a[x]; // 乘法
    if(i == 4) return sum / a[x]; // 除法（整除）
}

// 深度优先搜索（DFS）函数：尝试所有可能的运算符组合
void dfs(int x, int sum) {
    // 如果已经使用了4个运算符并且结果等于n，计数加1
    if(sum == n && x == 5) {
        ans++;
        return;
    }
    // 如果使用的运算符超过4个，返回
    if(x > 4) return;

    // 尝试每种运算符
    for(int i = 1; i <= 4; i++) {
        int num = cal(sum, i, x); // 计算当前运算结果
        dfs(x + 1, num); // 递归调用，继续尝试下一个运算符
    }
}

int main() {
    for(int i = 1; i <= 4; i++) cin >> a[i]; // 输入4个小于10的正整数
    cin >> n; // 输入目标值n
    dfs(2, a[1]); // 从第二个数开始进行DFS
    cout << ans; // 输出满足条件的方法数
    return 0;
}