Saturday, September 15, 2012

Recursion find best combination in an array that is equal to a given sum


//Recursion

#include <stdio.h>

int search(int *a, int n, int sum, int sel[], int fillim)
{
    int i;
    if(sum == 0)
    {
        return 1;
    }
    for(i=fillim; i<n; ++i)
    {
        if((sel[i]==0)&&(a[i]<=sum))
        {
            sel[i]=1;
            if(search(a, n, sum-a[i], sel, i+1)==1)
            return 1;
            sel[i]=0;
        }
    }
    return 0;
}
void print(int *a, int n, int sel[])
{
    int i;
    for(i=0;i<n;++i)
    {
        if(sel[i]==1)
        printf("%d \n", a[i]);
    }
    printf("\n");
}

int main()
{
    int a[100], sel[100], n, i , shuma;
    printf("Ju lu tem shkuarni n: ");
    scanf("%d", &n);
    for(i=0;i<n;i++)
    {
        printf("\n give the element  %d", i);
        scanf("%d", &a[i]);
    }
        printf("pls give the sum");
        scanf("%d", &shuma);

    for(i=0;i<n;i++)
    sel[i]=0;
    if(search(a, n, shuma, sel, 0)==1)
    {
        print(a, n, sel);
    }

}

No comments:

Post a Comment