c - C中的子集和递归

Question

我写了这个函数，但它只适用于非负整数。

int is_sum(int x, int a[], int n)

    {
        if (x == 0)
            return 1;
        if (n==0)
            return 0;

        return is_sum(x-a[n-1], a, n-1) || is_sum(x, a, n-1);
    }

我怎样才能让它对负整数起作用，我怎样才能跳进 2？

int is_sum(int x, int a[], int n)

    {
        if (x == 0)
            return 1;
        if (n==0)
            return 0;

        return is_sum(x-a[n-1], a, n-1) || is_sum(x, a, n-1);
    }

Answer 1

试试这个解决方案:

int isSubsetSum(int a[], int n, int sum)
{
   if (sum == 0)
     return 1;
   if (n <= 0)
     return 0;

   return isSubsetSum(a, n-1, sum) || 
                        isSubsetSum(a, n-2, sum-a[n-1]);
}