c - C中的递归函数查找任意数字N的算术组合

Question

我正在学习C。我的问题如下:给定一系列数字

1 *+ 2 *+ 3 *+ 5 .... *+ 9

或

其中数字 n 可以由 1 到 9 中的任意数字通过加法、乘法或两者的任意组合来创建，例如:

1 + 2 + 3 + 4 * 5 * 6 * 7 * 8 * 9 = 60486

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45

显然，存在可以通过上述各种组合来表示的数字集合。我的递归函数应该返回数字 N 在上述格式中具有多少种不同的唯一表示形式。

到目前为止，我一直在解决这样的解决方案:

int recCheckSolutions(int n, int idx, int tree[], int cnt, int sum)
{
    if (n == sum)
        return 1;
    if (idx > 9)
        return 0;
    if (sum >= n)
        return 0;
    cnt += recCheckSolutions(n, idx + 1, tree, cnt, sum += idx);
    cnt += recCheckSolutions(n, idx + 1, tree, cnt, sum *= idx);
    return cnt;
}

函数的调用方式如下:

int solutions = recCheckSolutions(n, 0, tree, 0, 0);

其中 n 是我们想要找到组合的所需数字 sum 是整数变量，用于查看我们的计算进度 tree[] 是我用来检查已计算哪些数字的树的实现(显然在此实现中不再相关，但仍然有用？)

它有一些正确的行为，我已经完成了堆栈跟踪/调试，它似乎有一些解决方案，但是，它并没有以正确的结果终止。我很可能找错了树。

非常感谢您的反馈和帮助。

Answer 1

除了返回条件之外，您已经做对了大部分事情:

int recCheckSolutions(int n, int idx, int tree[], int cnt, int sum)
{
    if (idx == 9)
        return 1;
    cnt += recCheckSolutions(n, idx + 1, tree, cnt, sum += idx);
    cnt += recCheckSolutions(n, idx + 1, tree, cnt, sum *= idx);
    return cnt;
}