Subset sum easy (doubt)

#1

please tell me what wrong I am doing in applying recursion and backtracking
Link for the code : - https://ide.codingblocks.com/s/105899
Link for the ques : - https://hack.codingblocks.com/contests/c/916/136

#2

@gsinha783
First of all remove the second if condition where you are checking sum == 0 outside the if(i>=n) block. This condition will always hit true in the first call as sum is 0 when we first call the function and thus your code will always return true.
Secondly , even if we hit the base condition when sum == 0 in if(i>=n) block , you return true , but it doesn’t matter as you do not return it further. There is no return statement for the recursive calls. Whatever result is produced in the recursive calls is lost as you simply do not return it further back to the parent calls and is thus useless.
Thirdly , you are forgetting that there is always one subset which is the NULL subset. The sum of the NULL subset , subset having no elements will have sum = 0 always and thus your code will always return true for it.

Modify your code considering these cases and share it again.

Suggestions : Make a vector of vectors in which you store all the subsequences. The maximum size of this will be 16 as n<=4 in this problem. Do not consider the vector with size() == 0. If you are including any element , append it into the vector and leave it if you are not. Any vector having sum of elements == 0 prints yes , otherwise print no if there is no such vector.

#3

I am storing it in an integer array. So how will I get a NULL subset? Are you saying that if I do not select any element of array then it will be a NULL subset, is it so?

#4

@gsinha783
Yes , that is exactly what I am saying . Your recursive calls will generate a subset in which sum of no elements would be counter i.e. the NULL subarray. Since it never counter any elements , the sum would always be 0 and every array would always have a NULL subsequence . We have to give our answer while ignoring this NULL subsequence.

#5


Please check it again.

#6

@gsinha783
The problem regarding NULL subarray stil wasn’t resolved.I have modified your code to account for that using a flag variable which marks that atleast one element has been counter while taking the sum.
Check it out here - https://ide.codingblocks.com/s/105950
And let me know if you have any problems regarding it.

#7

bool atleastOneIncluded, this variable is just for the case of NULL subarray, Am I right?

#8

@gsinha783
Yes.
For all other subsets , it would be true except for the NULL subset . That way , we can make sure that the NULL subarray does not get counted for the final answer.

#9

Thank you very much. How can I improve my solving ability for the questions on recursion and backtracking?

#10

@gsinha783
Recursion is a tricky topic which might seem difficult at first. I would suggest you to practice all the question in your HackerBlocks contest and Online Portal Challenges first. If that doesn’t make you confident about your Recursion coding skills and want more practice problems , refer to this Recursion specific contest - hack.codingblocks.com/contests/c/714
There’s more questions on this contest to master Recursion in and out with all sorts of problems.
Further I would suggest you to watch this Webinar for explanations and to understand how to approach the Recursion problems .
https://www.youtube.com/watch?v=UaN9WJtbHFY&t=2209s

#11

@gsinha783
Please mark your doubt as resolved if you are satisfied with the support in your Doubts Section. Or let me know if you need any further help regarding your issue.