can you please explain the whole recursion tree during the process,I have seen the solution for this question ,still not 100% clear about how the process is taking place,this will help me in understanding the concept in a better way.
Doubt in recursion tree
You can apply the following algorithm:
i : is the index of the current element
use two recursive statements:
first will be including the current element in the subset.
second will be not including the current element in the subset.
For base condition:
when i becomes equal to the length of the array,
check if sum is equal to zero: return true
else return false.
Try to implement this code.
why are we first writing the statement including the current element in the subset
and then excluding the current element,why can’t we do the opposite.
and explain about base case.
I have done the code but doubt in these concept
For every element we have 2 choices, either to include it in our subset or to not include it. The code should work correct either ways. The order of statements won’t matter.
Base condition is the condition we put to prevent array index to go out of bounds.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
At each step during the recursion , we make a call once where we include the current element into our sum and another where we exclude. If at the end when we reach the end of the array , we have obtained the sum=0, we return true , else false. During the intermediate recursive calls , we check the result from both the recursive calls , one including the current element and one excluding and return their OR since even if one of them had the subset sum 0 then we have to return true.
Note that the NULL subset ( subset with no elements ) is not to be considered as that would always have sum 0. To avoid considering that , we take a flag variable bool included = false and mark it as true even if we include a single element. Else it remains false. The NULL subset would be the only subset where the flag would remain false. For all other subsets , they would have included atleast one element and hence their flag would be true.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.