Subsets (LeetCode 78) | Full solution with backtracking examples | Interview | Study Algorithms
Vložit
- čas přidán 29. 07. 2024
- To see more videos like this, you can buy me a coffee: www.buymeacoffee.com/studyalg...
This could very well be your first backtracking problem. Given an array of unique elements, find the total subsets that can be possibly made. To find these subsets, you need to decide whether you should pick an element or leave it. Making this choice for each elements creates a state space tree and you then derive your solution. Backtracking makes this easy, and in this video we see how all of this works with animations and visuals. You will also find a dry-run of the code in JAVA
Actual problem on LeetCode: leetcode.com/problems/subsets/
Chapters:
00:00 - Intro
01:14 - Problem statement and description
03:30 - Logical approach to find all the subsets
06:45 - Backtracking solution to find all subsets
10:52 - Dry-run of Code
14:38 - Final Thoughts
📚 Links to topics I talk about in the video:
Recursion: • Recursion paradigms wi...
Brute Force Paradigm: • Brute Force algorithms...
Backtracking Paradigm: • Backtracking made easy...
What is Big O?: • Big O Notation Simplif...
📘 A text based explanation is available at: studyalgorithms.com
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
📖 Reference Books:
Starting Learn to Code: amzn.to/36pU0JO
Favorite book to understand algorithms: amzn.to/39w3YLS
Favorite book for data structures: amzn.to/3oAVBTk
Get started for interview preparation: amzn.to/39ysbkJ
🎥 My Recording Gear:
Recording Light: amzn.to/3pAqh8O
Microphone: amzn.to/2MCX7qU
Recording Camera: amzn.to/3alg9Ky
Tablet to sketch and draw: amzn.to/3pM6Bi4
Surface Pen: amzn.to/3pv6tTs
Laptop to edit videos: amzn.to/2LYpMqn
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #interview #backtracking
Even though you explained the intuiton, but you didn't explain recursion part of the code with dry running it. You said just forget the recursion part.
yeah he is trash. Never explains the code properly.
If you try dry running the code on your own you will understand it though.
yes he did not explain recursion part
he said forget the recursion part for the time being, but instead he forgot😂
Rarely do I comment on videos, but I must in this case. This video is beyond excellent. It is a clear and detailed explanation that covers not just the code solution, but the thinking behind it. Well done, and thank you
This was really helping Sir, thanks so much.
thanks for the amazing explanation!
todays leetcode problem, so went to this channel
backtracking part top notch explanation !
loved it!!Thankyou bhaiya
Nice bro!! The perfect path is followed to make sure that everyone can understand. Explaining the code will not fully help to understand recursion, dry run is the crux to completely get aware of the process. Thanks for the video!!
glad you liked it.
excellent explanation
thanks brother for ur explanation
finally understood after watching your video
thanks alot bhaiya very nice solution very easy to understand. Please clear my only doubt I have
why ---> resultSet.add(new ArrayList(tempSet)) why this statement execute for {1,2,3} subset for the first time instead of storing
{ empty }, then {1} then {1,2} then finally {1,2,3} why that above statement got skipped when we call the backtrack( ) function with start value 0,1,2 and it got execute for the first time when the start value was 3 why is that so???
Please tell me where I'm making mistake in understanding this part it will be really helpful bhaiya if u can help me with that.
Nice Explanation
thank you
How come sir the backtracking is calling that last line everytime even if the condition gets failed on the loop. I have faced this same confusion in the permutation problem as well. When the loop value ends how come the last line gets executed after that instead of breaking the entire loop. Actually if the recursive method is getting called on top of that last line the last line should not even get executed right even for once. Can you explain that part alone in detail.?
it does not break. it resumes to the initial call where the recursion actually started.
Nice video sir
Sir, you said to watch previous backtracking videos.
Where is the link of previous videos.
I don't even find any playlist for backtracking in your channel.
Would you please help me in mastering the concept of backtracking???
check the video description for more links. Here is the link to backtracking concept video: czcams.com/video/51Zy1ULau1s/video.html
Where is recursion part ?
Great Video thanks
Glad you enjoyed it
yur voice is damn cool love you bro
In the for loop, when we remove the number in the " // Case of not including number", why do we not call backtracking again?
In order to append a subset to the resultSet, we must call backtracking.
EDIT:
I got the answer. The case of not including a number is already added to the resultSet from the resultSet.add(tempSet) that comes before the for-loop.
glad you worked it out 😄
i am very lucky because i found this chennal
thanks sir u are osm
For in recurssion I'm not able to understand it
what part are you facing a problem with?
Super
i was not understood the recursive part clearly
Can never find someone who explains recursion well. Order of operations? If you read the loop the way it looks, it's like it does resultList = [[], [1], [1,2], [1.2.3]] and then in the last line, removes 3 to leave tempSet = [1,2]. Then the entire code stops because i = 3, condition breaks. So how are the other four subsets got? Also, how do you not end with two of [] in the result?
the condition does not break, you return to the last point where the function was called.
Visualizing recursion is always very tricky, it is hard to say but you need to get a feel of where the call would return.
Watch my video on recursion based algorithm paradigms...that gives a little food for thought: czcams.com/video/FTTHkmnvzlM/video.html
really man your explaination seems good, but voice is so low, that I can't hear anything clearly.
thanks for the feedback. I have been improving on it. Can you try listening to my latest video and tell if that quality is ok?
your explaination is very clear and understanble sir,Am so thankful for that.But I feel very difficult to apply recursion even after watching many youtube videos,I am still not able to understand how data is stored and returned in recursion.Could you please give some suggestion to learn sir?
recursion is never easy to understand. Even I face problems with it. Only thing I can say is that the more problems you solve, the more patterns you will see, and that will help you.
Also, every recursive problem can be solved iteratively ;)
@@nikoo28 ok sir thank you
I feel that this explanation could be improved compared to all your other material. There is a big disconnect between the intuition and the code. I think you said 'forget about recursion' then never got back to explaining it. Based on the tree diagram, it leads us to believe that 15 func calls are made but in reality only 8 func. calls are made? I added a 'funcCallsCount' and incremented each time we enter a function.
Suggestion:
-I think that using a debugger along with this would have helped; especially, after we remove item from 'tempSet', what happens next.
Perhaps that might seem like a lot but it will be much more beneficial. In the case of time, i think u can just explain the left subtree and that should be good enough.
I understand the confusion...and I will try re-iterate over this code at some point in the future. Thanks for your feedback
felt the same about the video
Misunderstood the code! My previous comment was a bit unpolite and hateful! I hope, man, you're ok with such negative comments!
thanks for the explanation.
I spent couple of hours to resolve these backtracking algorithms. And this was emotional comment!
And thanks for the positive reply.
ps initial comment is updated
Why do you feel the code does not work? It passes all the test cases on LeetCode. Did you have a look at the full code on Github? It is available in video description. Please let me know
@@nikoo28 Bro ignore him and chill💫
@@nikoo28 this is my fault! thanks for the reply!
I must to admit that it works!!!
Will remove comment!
@@Ramires2no worries, always receptive of critical feedback 🙂 my best wishes with your coding journey
bro u did not explain the recursive part its confusing please make another video
i will make a general video on how to approach such problems. They all have a similar pattern.
@@nikoo28 thank you 😊
Your code and diagram do not match. The diagram that you have shown, we will only add to the powerset at the last level.
But in your code, you keep adding to your powerset at every level.
According to your code, in your diagram, there should be 3 children of the root node.
[ ]
/ l \
[1] [2] [3]
That is not the case, I do not add all 3 child nodes to the root in the beginning.
If you look at the code again you add one number to the set and then call the backtrack method again.
@@nikoo28 Thanks for the quick reply, yes, that is what my point is. According to your code, you are adding ALL the nodes of euler tree to the powerSet.
This means there will be duplicates in your powerset. See for example the first 3 levels:
[ ] { [ ] }
/ \
[ 1 ] [ ] { [ ], [1], [ ] }
/\ /\
[1,2] [1] [2] [ ]
final pwrset = { [ ], [1], [ 1, 2 ], [1], [ ], [2], [ ] }
At the last level, you wil have added 15 total subsets in your powerSet(from all levels) as opposed to the 8 subsets(only from the last level).
You are confusing the recursive approach where you add to the powerset only at the LAST level once the current subset has been fully generated.
vs. the backtracking approach where you add at EACH level(each node) and never repeat the same node once it has already been exhausted by deleting it.
Please refer to this leetcode comment for the actual euler tree your code corresponds with:
leetcode.com/problems/subsets/discuss/27281/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)/26331
Thanks for your time and discussion, let me know your thoughts
EDIT: You could test it out by maintaining a counter in your method signature. Increment the counter each time you visit a node(recursion call)
Using your code, counter would = 8
But in your diagram, counter will be = 15.
I am still failing to understand...in my diagram at 7:33, I pick up the element, and doing the same in code....after that in the diagram....I backtrack...and then chose not to pick the element at 7:37...the same is reflected in the code as well. So I am unable to understand why you say that the code and diagram do not match.
I understand the count part...yes there will be duplicates in the final result set, but for this particular question it is fine.
@@nikoo28 You can not traverse breadth first in a recursive call stack. So your idea of selecting the left branch, then going to the right branch is wrong.
You will go depth first, and at the leaf node, you will add it the currentSubset to the powerSet.
As I said, in your code, you are only generating 2^n( =8 in this case) nodes in the tree, it is not even a binary tree like in your diagram. But it is a tree as shown in the diagram I have linked you.
In your recursive diagram, it is a binary tree with total of 2^n * 2 - 1 nodes. (=15 in this case)
According to your code, you are adding every node with resultSet.add() on EVERY recursive call, meaning you will add 15 subsets in your result set.
To have a diagram and logic that you are using,
your code should have been something like this(pardon the formatting and pseudoness, I'm on phone):
powerSet(){
if( idx == nums.length )
{
resultSet.add()
return;
}
//selecting
currentSubset.add(nums[idx]);
powerSet( idx +1, nums, resultSet, currentSubset);
//removing the added element for "backtracking"
currentSubset.remove(size-1)
//"backtracking"
powerSet( idx +1, nums, resultSet, currentSubset);
}
}
yes exactly that is what happening when i try running the code. it is printing all the nodes resulting in duplicate values.
📌📌📌📌when the element enter into the for loop, it always enter into the recursion part... it never enter at the temp.remove part .........
can u plz explain, how this loop works.....
in the video, you said ....now, don't see the recursion part , just see what happening in the remove part... but at last u can't explain it
The temp.remove part will execute once the recursion has finished. There will be a case when you will recurse..and you will not enter the for loop.
The value of “start” will be equal to nums.length.
That is when a recursion ends and you will reach the remove part.
@@nikoo28 Remove part is present inside the loop, when the loops fails, it will not enter into the loop... then how the elements access the remove part? ?? 🤔🤔🤔🤔🤔🤔
@@gokulakannan3664 exactly…when it will not enter the for loop…this is when the previous recursion call ends…and then the remove statement from the previous call gets executed
your voice is so low, bro, could even hear you without headphones.
Not efficient enough.