mercredi 1 juillet 2020

How can I apply memoization to this recursive function?

I was solving the Subset Sum problem: "Given a set of numbers, check whether it can be partitioned into two subsets such that the sum of elements in both subsets is same or not." For this problem I created a recursive function which works correctly but I am not able to correctly memoize it.

The code is:

bool func(int a[], int i, int n, long sum) // i is 0, n is the array size, sum is required sum
{

    if(sum<0||i>=n)
      return 0;
    if(sum==0)
      return 1;

    if(func(a,i+1,n,sum-a[i]))
      return 1;
    if(func(a,i+1,n,sum))
      return 1;

    return 0;
}

Please help in memoizing this code. Also can you tell that which is better for these type of problems recursive code with memoization or tabulation.

Aucun commentaire:

Enregistrer un commentaire