【题目】计算未知等式的可能性（dfs）

本子上有一些数学等式，但是所有的运算符都没了。如：“3□1□2”（□表示被划掉的运算符）。
其中
1.每个□代表‘=’、‘-’、‘+’三个符号之一；
2.等式中有且仅有一个‘=’；
3.需要满足一个等式。如“3-1=2”。
计算满足该等式的可能性有多少。

输入：
输入一个数字n（2<=n<=15），代表等式可以看到n个数字。接着输入n个数字。保证每个数字都是非负整数，且小于10^5。

输出：
输出一个整数，表示该等式的可能性有多少。

示例1：
输入：
3
3 2 1
输出：
2

示例2：
输入：
4
1 1 1 1
输出：
6

主要代码段：

int tempLeft[10000];
int leftCnt = 0;
int tempRight[10000];
int rightCnt = 0;

int FindSameNumber(int *left, int leftCnt, int *right, int rightCnt)
{
    int res = 0;
    for (int i = 0; i < leftCnt; i++) {
        for (int j = 0; j < rightCnt; j++) {
            if (left[i] == right[j]) {
                res++;
            }
        }
    }
    
    return res;
}

// 从start到end遍历各种可能的结果
void dfs(int start, int end, int value, int *nums, int *temp, int *count)
{
    if (start == end) { 
        temp[*count] = value;
        (*count)++;
        return;
    }
    
    dfs(start + 1, end, value + nums[start + 1], nums, temp, count);
    dfs(start + 1, end, value - nums[start + 1], nums, temp, count);
    
    return;
}

int FindMaxNum(int *nums, int n)
{
    if (n == 2) {
        return nums[0] == nums[1] ? 1 : 0;
    }
    
    int res = 0;
    leftCnt = 0;
    rightCnt = 0;
    
    for (int i = 1; i < n; i++) { // 在nums中从左到右放等号。
        leftCnt = 0;
        rightCnt = 0;
        dfs(0, i - 1, nums[0], nums, tempLeft, &leftCnt);
        dfs(i, n - 1, nums[i], nums, tempRight, &rightCnt);
        res += FindSameNumber(tempLeft, leftCnt, tempRight, rightCnt);
    }
    
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    int nums[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    
    int a = FindMaxNum(&nums, n);
    
    printf("%d\n",a);
    
    return 0;
}

yo peace！