C练习任务(递归)

Question

我一整天都在为以下问题而苦苦挣扎。我一开始就有问题。我不知道如何使用递归来解决这个特定问题。我将非常感谢您的帮助，因为我的期末考试还有几天。干杯

假设有一个包含“n”个元素的整数数组“a”。编写递归函数 sumExists 如果可以将 m 写为元素之和，则对于给定的数字 m 返回 1数组 a 的数组，如果不是，则为 0。数组“a”中的元素只能使用一次。函数 sumExists 的原型(prototype)是:int sumExists( int a[] , int n, int m );

示例:

a[5] = { 15, 9, 4, 2, 1 } , n=5, m=17. Function sumExists returns 1;

a[5] = { 15, 9, 4, 2, 1 } , n=5, m=8. Function sumExists returns 0;

代码:

int sumExists(int a[],int n, int m) {
    int i;
    if(m == 0) return 1;
    for(i = n-1; i >= 0; i--) {
        m = m - a[i];
        if(sumExists(a,i,m)) return 1;
    }
    return 0;
}

Answer 1

试试这个:

int sumExists(int a[], int n, int m) {
    if (n == 0)
        return m == 0;
    return sumExists(a, n - 1, m - a[n - 1]) || sumExists(a, n - 1, m);
}

递归检查:

是否存在与 n-1 元素的总和(因为使用大小 n-1 调用并减去 a来自 m 的 [n-1]。就好像在总和 m 中包含 a[n-1])。

或

如果 没有 n-1 元素的总和(跳过 a[n-1] 并使用 a 检查[1..n-1]).