I could not understand the algorithm for this problem. Somone explain this code plz
bool isSubsetSum(int set[], int n, int sum)
{
bool subset[sum+1][n+1];
for (int i = 0; i <= n; i++)
subset[0][i] = true;
for (int i = 1; i <= sum; i++)
subset[i][0] = false;
for (int i = 1; i <= sum; i++)
{
for (int j = 1; j <= n; j++)
{
subset[i][j] = subset[i][j-1];
if (i >= set[j-1])
subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1];// ???
}
}
return subset[sum][n];
}
above solution uses the concept of dp:over here index i of array subset represents sum to be made,
while j index represents index till which numbers from our original array(in this case set) is to be taken.for e.g. subset[5][4] represents we have to make sum of 5 by using elements 1…to…4 of array.
subset[0][i] has been set to 1 which represents that sum of 0 can be made in any case,while subset[i][0] has been set to 0 which means any sum greater than 0 cannot be made without selecting any numbers.
subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1];
what this line is basically doing ( can be best explained from given example below):
if our set is {9,2,1} and want to check if sum of 10 can be made from given array:
then firstly subset[1][3] would be set to 1,
secondly subset[9][1] would be set to 1
lastly subset[10][3] would be set to 1
last would be computed as follow:
subset[10][3]=max(subset[10][2]||subset[10-1][3-1])
since subset[10-1][3-1] has already been computed to 1
so result of subset[10][3] would also be 1
so we are finally able to compute that 10 can be formed from given array
if you specifically want to know about problem asked in codex than you can refer to editorial of FBRSUM in JAN14 long contest…