CODEWITHSUNDEEP
carraysrecursionsum
user2301925
user2301925

Reputation: 13

C practice task (recursion)

I've been struggling with the following problem for a whole day now. I have problems at start. I can't figure out how to use recursion for this particular problem. I will really appreciate the help since my final exam is in few days. Cheers

Let there be an integer array "a" with "n" elements. Write recursive function sumExists which will for given number m return 1 if it's possible to write m as sum of elements of array a, or 0 if it isn't. Elements from array "a" can be used only once. Prototype for function sumExists is: int sumExists( int a[] , int n, int m );

Example: 

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;

Code:

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;
}

Upvotes: 1

Views: 162

Answers (1)

Elad
Elad

Reputation: 753

try this:

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);
}


The recursion checks:

whether there is such a sum with the n-1 element (since calling with size n-1 and subtracting a[n-1] from m. as if to include a[n-1] in the sum m).

or

if there's such a sum without the n-1 element (skipping a[n-1] and checking with a[1..n-1]).

Upvotes: 3

Related Questions