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