Great video, although I still don't understand why the space complexity is O(n). I understand that the call stack is O(n), but we're also storing the results in the res list, whose length scales with n. With the example of 3 inputs, we have 2**3 results in the results list, and each result has up to n length. Shouldn't the space complexity therefore be O(n*2^n)
Because we store only n number of call stacks at max , the count will always be balanced as we also backtrack(pop the last call) and call a new stack, try referring a tree structure - you will have more insight...
@@gordonz4762 thanks for editing the ask that actually resolves ,and the answer for your question is they can actually print the subset at the base condition check each time, but the way greg solved requires that extra space
Glad it's not just me who has had trouble understanding recursion. But it's a good building block for understanding harder problems, like ones involving dynamic programming.
@@JoatXI He probably means conceptually. I would say let the idea about selecting and unselecting be clear in the arguments or function calls. So, in this branch, it is selected. In the other branch, it is unselected. Then, there are fewer global variables to keep track of. Greg's approach is like backtracking for 1-tree or reversing a single-linked list by recursions that can be done easily through combinations API or reversing API. One is probably working on advanced skill sets if one is using this approach. However, global or nonlocal keywords are discouraged at the moment. There are indeed many hard problems. So, one just needs to be very patient to go through the code step by step or purchase a premium to use the debug feature. In my case, I would work on beginner problems mostly.
Master Data Structures & Algorithms For FREE at AlgoMap.io!
I appreciate you making the vid greg! vids that explain a concept/algo and then show an example are very useful, not many people doing that
Nice. Explanation. I might have a question but I still have to think about it.
5:52 he better call 'sol'
this problem came in my coding interview but instead i had to just output the number of subset so i just printed 2 to power n
I don't think anyone could explain this better fr
Thats nice, really good explanation!
7:40 , so basically, we are doing inorder traversal right?
Yup
This solution is brilliant
i think the time complexity should be 2^n * n right ?
Total number nodes in the tree = (2^0+2^1+...+2^n) = 2^(n+1) - 1. So, Time complexity is O(2^n).
You said youve covered videos om DFS but I went through your playlist and didn't see it, please can you send me the link
Great video, although I still don't understand why the space complexity is O(n). I understand that the call stack is O(n), but we're also storing the results in the res list, whose length scales with n. With the example of 3 inputs, we have 2**3 results in the results list, and each result has up to n length. Shouldn't the space complexity therefore be O(n*2^n)
Because we store only n number of call stacks at max , the count will always be balanced as we also backtrack(pop the last call) and call a new stack, try referring a tree structure - you will have more insight...
@naveenreddy8691 Yes the call stack is O(n), but the results list also takes space no?
@@gordonz4762 thanks for editing the ask that actually resolves ,and the answer for your question is they can actually print the subset at the base condition check each time, but the way greg solved requires that extra space
Very hard
Nobody got me like Greg Hogg got me
Hardest sht in coding
Yeah it probably is
Glad it's not just me who has had trouble understanding recursion. But it's a good building block for understanding harder problems, like ones involving dynamic programming.
First view 😊😊
I tried this, and it didn't even work.
if you tried it in leetcode and it didn't work, make sure your coding language is Python3 and not just "Python"
@@JoatXI He probably means conceptually. I would say let the idea about selecting and unselecting be clear in the arguments or function calls. So, in this branch, it is selected. In the other branch, it is unselected. Then, there are fewer global variables to keep track of.
Greg's approach is like backtracking for 1-tree or reversing a single-linked list by recursions that can be done easily through combinations API or reversing API. One is probably working on advanced skill sets if one is using this approach. However, global or nonlocal keywords are discouraged at the moment.
There are indeed many hard problems. So, one just needs to be very patient to go through the code step by step or purchase a premium to use the debug feature. In my case, I would work on beginner problems mostly.