For the ppl like me who struggled with grasping the dfs recursive call, below is a simple example: Let's say we have the list nums = [1, 2, 3] and we call the dfs function with i = 0. The first call: dfs(0): The condition i >= len(nums) is false, so we move forward. nums[0] is appended to subset which is now [1]. A new call is made to dfs(1). The second call: dfs(1): The condition i >= len(nums) is false, so we move forward. nums[1] is appended to subset which is now [1, 2]. A new call is made to dfs(2). The third call: dfs(2): The condition i >= len(nums) is false, so we move forward. nums[2] is appended to subset which is now [1, 2, 3]. A new call is made to dfs(3). The fourth call: dfs(3): The condition i >= len(nums) is true, so the current subset [1, 2, 3] is appended to the res list. The function returns. The third call returns: nums[2] is removed from subset which is now [1, 2]. A new call is made to dfs(3). The fifth call: dfs(3): The condition i >= len(nums) is true, so the current subset [1, 2] is appended to the res list. The function returns. The second call returns: nums[1] is removed from subset which is now [1]. A new call is made to dfs(2). The sixth call: dfs(2): The condition i >= len(nums) is false, so we move forward. nums[2] is appended to subset which is now [1, 3]. A new call is made to dfs(3). The seventh call: dfs(3): The condition i >= len(nums) is true, so the current subset [1, 3] is appended to the res list. The function returns. The sixth call returns: nums[2] is removed from subset which is now [1]. A new call is made to dfs(3). The eighth call: dfs(3): The condition i >= len(nums) is true, so the current subset [1] is appended to the res list. Hope this helps! And thanks Neetcode for sharing the original solution!
@gggeeh
Жыл бұрын
Thank you for the explanation! It's really helpful :) Can I ask after the dfs(3), where condition i >= len(nums) is true, how does it know to return to dfs(2)? Shouldn't the code dfs(i-1) be added after return? Original code: def dfs(i): if i >= len(nums): res.append(subset.copy()) return subset.append(nums[i]) dfs(i + 1) subset.pop() dfs(i + 1)
@prodsefv
Жыл бұрын
@@gggeeh Let's consider the example of the dfs function in the given code. When the function is first called with dfs(0), a new instance of the function is added to the call stack. This instance starts executing and calls dfs(1), which in turn calls dfs(2), and so on. When the innermost call to dfs(3) returns, it pops off the call stack, and the control returns to the previous instance of the function, which was waiting for the call to return. The previous instance then continues executing from where it left off, which is the next line of code after the recursive call that just returned. In the example you asked about, after the call to dfs(3) returns, the control is returned to the previous instance of the dfs function, which was dfs(2). The code then continues executing from where it left off in the dfs(2) call, which is the next line of code after the dfs(3) call, which is subset.pop(). This line removes the last element from the subset list, and then the code continues with the next line, which is the next recursive call to dfs(3).
@tinymurky7329
Жыл бұрын
mind blowing! Thx
@apollodavis4090
Жыл бұрын
what about [2], [2,3] and []?
@vaishnavinatarajan3987
11 ай бұрын
Really helpful. Great work !!
@zoidian601
2 жыл бұрын
This is a great video. These backtracking solutions are so hard to understand for some reason. I wish there was an in-depth video about converting general decision trees to these backtracking algorithms
@devenderbhatt421
10 ай бұрын
Its hard but if u just take an example and run through his function u will get to know what exactly is happening
@radishanim
2 жыл бұрын
I struggled with understanding the reason for appending `subset.copy()` instead of `subset`. I think what is happening is, we need to append the actual instance of each modified subset `subset.copy()` instead of the reference which is pointing to the subset which gets modified. Neetcode's stated reason for appending the copy of the subset ("this subset is going to be modified, right?") is correct- the reference will be pointing to a subset that keeps getting modified, which will eventually make the function return a list of empty subsets. tl:dr; res.append(subset.copy()) actually appends [1,2,3] to the res. res.append(subset) appends the pointer to the subset which at the time may be [1,2,3] but will eventually be [] due to us popping (aka modifying) the subset. If this didn't make sense, try adding `print(subset, subset.copy())` at line 7 and `print(res)` at line 9 and 19. That might clarify the situation.
@easynow6599
2 жыл бұрын
Nice explanation..an easy way to demonstrate that is: list1 = [1, 2] list2 = [] list2.append(list1) list1.pop() print(list1) #prints [1] print(list2) #prints [[1]]
@blossombabalola1234
2 жыл бұрын
Thank you for this explanation, this makes sense
@jayeshpatil8408
2 жыл бұрын
Thanks for the explaination! I didn't get it before! :)
@itachid
Жыл бұрын
If you know how to debug python files, you can replace subset.copy() with subset and use VSCode (or any IDE) to run the debugger and see the res being changed with respect to subset because it's a reference to it.
@RajPatel-is8em
Жыл бұрын
Thanks, buddy!
@localstreamers1054
3 жыл бұрын
Backtracking and choices have always been difficult for me. After watching and understanding your explanations, I am able to solve at problems like subsets, permutations with looking at the code at a all. thanks a lot for your work.
@Sportsandgames6
2 жыл бұрын
This is great, but I noticed 2 things: 1) I don't think this is backstracking, this is just full recursion DFS. Backtracking is when you pre prune a tree by not going down a certain path with DFS if the partial solution at that level is already wrong (so you backtrack away). 2) line 16, the pop() doesn't represent NOT including it, that wouldn't be an inaccurate way to think about it. What its doing is restoring the state of the slate "subset" to the state it was in before the append inclusion happened. Another way to think about it, is if you switched the code lines for the decisions to include and exclude, you would think you don't need the pop() after calling the DFS on the exclude, when you still do. E.g: # decision NOT to include nums[i] DFS(I+1) # decision to include nums[i] Subset.append(nums[i]) DFS(i+1) Subset.pop() # you still need this line here even though you might not think you do Other than that, this was a great video, thanks!
@abdallashawkyabdo2721
Жыл бұрын
i totally second your opinon, and i don't know why are people call it backtracking :D, i thought i was only the one who has this opinion
@joya9785
Жыл бұрын
Great thanks for the explanation!!!
@pianopianist5709
Жыл бұрын
Can you share the backtracking solution then?
@user-fl9cx5ww5l
10 ай бұрын
great inspiration
@The6thProgrammer
10 ай бұрын
For your second point, I disagree. Surely you will need pop() no matter what because you need to explore the different combinations for the subset, but intuitively you can still consider pop() as excluding elements. Hence why the total count of subsets is 2^N, because at each element we have 2 choices (include or don't). For instance, at the beginning of the algorithm we have 2 choices for the set [1, 2, 3], either include [1] in the subset or do not. When the leaf nodes of the entire left subtree of the root are explored and control returns to our first function call this is what it looks like: index = 0 subset = [1] createSubset([1], 0 + 1) subset = [] createSubset([], 0 + 1) // Now explore all subsets without 1 So essentially we have used pop() to now to exclude 1, and begin to explore all subsets that do not contain 1. What you call "restoring state" is the exclusion of the element we added to allow us to explore the branch of the tree that does not contain that element.
@RichardLopez-lr4el
2 жыл бұрын
Just had a coding interview, and this channel helped me so much! Keep up the amazing work!
@user-xz8po2nv8p
6 ай бұрын
It looks like there is much simpler solution: def subsets(nums: List[int]) -> List[List[int]]: subs = [[]] for n in nums: for i in range(len(subs)): subs.append(subs[i] + [n]) return subs
@konradhunter1407
2 ай бұрын
This is how I did it. Much easier!
@rex1264
2 жыл бұрын
I searched many articles and videos to figure out the problem's time and space complexity. Many of them explain: there are two choices, choose it or not, so the time complexity is O(2^N * N). Only this video draws the recursion tree. I think it helped me realize complexity immediately.
@anishm8813
2 жыл бұрын
I used DP the same way as you used for Partition Equal Subset Sum. Code: class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res=[[]] for i in nums: new=[] for t in res: new.append(t) new.append(t+[i]) res=new return res Btw love your videos.
@ma_sundermeyer
2 жыл бұрын
yeah, I have a similar one, you don't even have to overwrite your results everytime: subsets = [[]] for n in nums: for i in range(len(subsets)): subsets += [subsets[i]+[n]] return subsets Combining every new element with all existing subsets feels just so much more natural and easier to understand.
@orellavie6233
Жыл бұрын
Who said that the input array has no duplicates? If that's true the solutions here are okay.
@dmitriyklyuzov4827
Жыл бұрын
@@ma_sundermeyer This seems like a much more intuitive solution to me, I came up with something very similar. Yours is very elegant. Good job!
@angelocortez1861
2 жыл бұрын
Had a coding interview recently ; though I didn't pass, with these videos, I definitely feel more confident. I got my first SWE job as an econ major, and have struggled with these concepts even though I took an algorithms class. I definitely feel like your videos taught them better than the professor.
@sucraloss
11 ай бұрын
I took some CS courses at a good university and for certain Neetcode explains these concepts much better than the tenured professors and their TAs with many years of programming experience.
@charanbathula984
2 жыл бұрын
about subset.copy() , if we use res.append(subset)--> res is [[subset],[subset]] so finally when subset is empty[], res will be [[],[]] if we res.append(subset.copy())--> res is [[1],[]] , used example when nums =[1]
@sap1363
3 жыл бұрын
This is pure gold exactly what I wanted. Thanks for creating this gem
@kylehench
Жыл бұрын
Easy solution using list.extend() and list comprehension: res = [[]] for num in nums: res.extend([item + [num] for item in res]) return res
@pradgarimella
3 жыл бұрын
Thanks for the amazing explanation. This feels like the 0/1 knapsack problem. There are multiple solutions to this problem, this is the cleanest approach I have seen
@rustyglen7708
3 жыл бұрын
Great video! I don't know how you find a way to explain hard problems so clearly. Thanks for uploading these!
@ilanaizelman3993
2 жыл бұрын
For people who are wondering why to use nums.copy() : Because the list nums is being modified during the function calls. If you just append it to the output you append a reference (pointer) to nums not the actual list which means that after nums is modified from some other recursive function it will be "changed" in the output list that stores the reference to nums. In the end, output will contain pointers that will point to the same result (whatever was the last change in nums). So you need to make a deep copy of nums. Note: If I'm not mistaken you can use nums[:] instead of nums.copy(), so we can still stay w/ Python2 instead of Python3..
@meowmaple
2 жыл бұрын
BRO, I was struggling with this question earlier when it kept appending new subsets to existing list, and was forced to watch this video as a result. After i found your comment and added .copy() to the working list that I pass to new dfs() calls, IT WORKED LIKE A CHARM. THANKS
@ilanaizelman3993
2 жыл бұрын
@@meowmaple u can use nums[:] as well
@Zeegoner
2 жыл бұрын
Uh, there is no nums.copy() in the entire video...
@Zeegoner
2 жыл бұрын
If you mean subset.copy() then your explanation makes no sense because subset is not modified once the base case (i >= len(nums)) is met.
@radishanim
2 жыл бұрын
@@Zeegoner I struggled with understanding the reason for appending `subset.copy()` instead of `subset` for a couple of hours as well. I think what is happening is, we need to append the actual instance of each modified subset `subset.copy()` instead of the reference which is pointing to the subset which gets modified. Neetcode's stated reason for appending the copy of the subset ("this subset is going to be modified, right?") is correct- the reference will be pointing to a subset that keeps getting modified, which will eventually make the function return a list of empty subsets. tl:dr; res.append(subset.copy()) actually appends [1,2,3] to the res. res.append(subset) appends the pointer to the subset which at the time may be [1,2,3] but will eventually be [] due to us popping (aka modifying) the subset. If this didn't make sense, I think adding `print(subset, subset.copy())` at line 7 and `print(res)` at line 9 and 19 might clarify the situation.
@Codenames560
2 жыл бұрын
wow 300 times better than other videos/leetcode solutions
@E1an9640
3 ай бұрын
for all people struggling with recursive code I assure you most of us have been in same situation initially but as you practice more problems (wont take too long if u r consistent) I assure that you will be surprised how naturally it comes to you
@venkateshgopalakrishnan3786
3 ай бұрын
reading this was really helpful. understanding recursion has been a nightmare for me. hopefully I get better by solving more problems
@lhsh3942
3 жыл бұрын
I was always running away from this question until saw this. Thanks for sharing this video~
@aditijain2448
Жыл бұрын
i just love that all your videos are under 20 mins
@almaspernshev7370
9 ай бұрын
Here what happens with subset during backtracking, which might help to understand it. append to subset [1] 0 append to subset [1, 2] 1 append to subset [1, 2, 3] 2 add to res: [1, 2, 3] 3 pop from subset [1, 2, 3] 2 add to res: [1, 2] 3 pop from subset [1, 2] 1 append to subset [1, 3] 2 add to res: [1, 3] 3 pop from subset [1, 3] 2 add to res: [1] 3 pop from subset [1] 0 append to subset [2] 1 append to subset [2, 3] 2 add to res: [2, 3] 3 pop from subset [2, 3] 2 add to res: [2] 3 pop from subset [2] 1 append to subset [3] 2 add to res: [3] 3 pop from subset [3] 2 add to res: [] 3
If it’s going to be O(n*2^n) anyway, loop i from 0 to 2^n-1 and divide i by 2 n times to decide which element to be included. You don’t need backtracking at all
@charleswandetu988
Ай бұрын
BFS def subsets(self, nums: List[int]) -> List[List[int]]: result = [[]] q = deque() for i, num in enumerate(nums): q.append((i, [num])) while q: i, array = q.popleft() result.append(array) for j in range(i+1, len(nums)): q.append((j, array + [nums[j]])) return result
@danny65769
3 ай бұрын
I actually think the time complexity is O(n^2 + 2^n), can someone criticize my logic? - the number of subset is 2^n, but the number of nodes in the binary decision tree is actually 2^(n+1) - 1. So time complexity to go through all nodes is O(2^(n+1) - 1), which simplifies to O(2^n). - at each leaf node (and there are (n + 1) / 2 leaf nodes in the tree), a copy of the subset is made. So time complexity here is (n+1)/2*n = O(n^2) - so final time complexity is O(n^2 + 2^n) , which can possibly reduced to O(2^n)?
@adityakulkarni5577
11 ай бұрын
The method for coding it up seems overly complicated. This solution on Leetcode helped me understand the problem much better. def generateSubset(nums): if not nums: return [[]] tail = generateSubset(nums[1:]) currentValue = nums[0] output = [] for subset in tail: output.append(subset) output.append([currentValue] + subset) return output return generateSubset(nums)
@DANIELEVI1234
2 жыл бұрын
Hello Neat Code! Your work is amazing and really helpful! Can you please elaborate about the Time and Space complexities? Thank you very much
@DANIELEVI1234
2 жыл бұрын
Neet** sorry! :D
@NeetCode
2 жыл бұрын
Hey appreciate the kind words! For Time it is O(n * 2^n) because there will be 2^n different subsets, and we have to create a copy of each one, which is O(n). For Space it is O(n) if you don't count the output array, because the size of the function call stack will be O(n). Meaning we have to call the recursive function n times in a row, before it returns.
@DANIELEVI1234
2 жыл бұрын
@@NeetCode Ah now it's clear, great! thank you!!
@rabbyhossain6150
3 ай бұрын
@@NeetCode that means, if there is no copying then it is O(2^n)
@tanmaymokal198
2 жыл бұрын
Your videos are so fun to watch and most imp they don't make me sleep.
@ridhachowdhury1831
Жыл бұрын
Hey guys, I'm a bit confused why this is classified as backtracking and not just regular recursion. We don't ever really hit a constrained choice and have to backtrack?
@bree9895
Жыл бұрын
yeah same qs
@pranaymandadapu9666
Жыл бұрын
Damn, the tree was exact how the recursion stack will create during recursion. But the only disconnect I felt was he explained how the tree is created from top to bottom, but during the program execution, the tree is created from bottom to top. It took me some time to wrap my head around it.
@kousikmitra7069
7 ай бұрын
Hey can you explain the how time complexity is O(n * 2^n) ?? Since the recursion is kind of working as a complete binary tree, should not it be O(2^(n+1))
@muskan_bagrecha
5 ай бұрын
probably due to the copy() operation
@noctua7771
Жыл бұрын
You're a legend at explaining things simply. Thank you!
@juliahuanlingtong6757
3 жыл бұрын
This solution is more intuitive to me than the for loop one! Exactly what i thought. Is it posisble to do a video on subset II (subset with duplicate) on top of this approach please? Looking forward to it!
@emmatime2016
3 жыл бұрын
I feel the same....
@chengjinfei8139
2 жыл бұрын
I saw a lot ways to solve this issue, but you are the most clean one. Thanks.
@bilalmohammad4242
Ай бұрын
I love you man. keep up the great work !
@stephentomaszewski8501
Жыл бұрын
can also just jsut an iterative solution: class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: # backtracking # time: O(n*2^n) # space: O(2^n) output = [] # base case output.append([]) # constraint: add n nums for num in nums: # choice: do or don't add the number to the list for i in range(len(output)): # don't add the number by appending the list with the current list output.append(output[i]) # add the number to the current list output[i] = output[i] + [num] return output
@TanishBansal-ss2ou
3 ай бұрын
Easier to understand: class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: subs = [] sub = [] def solve(i): subs.append(sub.copy()) for j in range(i,len(nums)): sub.append(nums[j]) solve(j + 1) sub.pop() solve(0) return subs
@hassan7569
Жыл бұрын
you don't need to add and then pop, you can just do dfs() and then do append + dfs(), which makes things more effecient. Also the >= comparison doesn't make sense, since you can't go over len(nums) so i == len(nums) if sufficient.
@surajslab984
2 жыл бұрын
Your videos are really awesome, the way u explain the problem by splitting it into different section is simply great !!
@KomalPal
2 жыл бұрын
@NeetCode Seriously thanks a lot, i can only understand recursive problems through recursive tree and thats why it takes me hard to analyse bcoz I have not much people to discuss for the same, srsly thanks a lot for doing the ques the same way it it understandable to me ☺
@abhicasm9237
2 жыл бұрын
Can someone explain me why we need to add the copy of subset there??
@deewademai
Жыл бұрын
backtracking question is the most difficult question to me. Where can I learn it and improve my skill with backtracking?
@elyababakova2125
Жыл бұрын
Mindblowing🤯 Thanks for explanation, very helpful!
@rajdipdas9413
2 жыл бұрын
we can also do this with bitwise manipulation where we will run a for loop from 0 to 2^n that is the no of subsets.
@randomtalks141
Жыл бұрын
Pls show the inner implementation of this code using stack I couldn't able to understand what is happening after poping out the element
@hoyinli7462
3 жыл бұрын
your code is super clean
@danielsun716
Жыл бұрын
Another two solution, slightly different, but very intuitive to beginner for understanding backtracking. # control for loop to end dfs func. so no need to add edge case # res, sub = [], [] # def dfs(i): # res.append(sub.copy()) # for j in range(i, len(nums)): # sub.append(nums[j]) # dfs(j + 1) # sub.pop() # dfs(0) # return res res = [] def dfs(i, sub): res.append(sub) for j in range(i, len(nums)): dfs(j + 1, sub + [nums[j]]) dfs(0, []) return res
@edwardteach2
3 жыл бұрын
U a God Here's my implementation without the need for subset.copy(), you'll just have to pass in the subset directly in the parameter as you create the subset recursively: class Solution(object): def subsets(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ res = [] def dfs(i,curr): # pass in the current idx and the current subset if i >= len(nums): # base case res.append(curr) # add the subset return dfs(i+1,curr+[nums[i]]) # to include nums[i] dfs(i+1,curr) # not to include nums[i] dfs(0,[]) # start at index 0 and with empty list return res
@SM-si2ky
2 жыл бұрын
The tree is really helpful! Cheers
@abhishektyagi3941
2 жыл бұрын
Amazing video superb explnation..please make a video on subset2 also..
@sidazhong2019
2 жыл бұрын
there is mistake, or i made a mistake. i think... # decision to include nums[i] subset.append(nums[i]) dfs(i+1) subset.pop() #pop() is for backtracking reason. it has to remove the old element from the subset before traversing a new path # decision NOT to include nums[i] dfs(i+1) # this is mean give a empty result, it doesn't do anything to subset.
@GmDoggie
5 күн бұрын
I'm still trying to internalize these concepts, and I could be wrong but, is your drawing following the order in a BFS way? Your solution uses DFS and it may be easier to understand the actual code if the drawing followed the same call order.
@michaelyao9389
2 ай бұрын
I think we can also do this recursively.
@ghodsiyeghanbari7040
Жыл бұрын
Thank you, It was well-explained and neat!
@ThangTran-hi3es
8 ай бұрын
Thanks for your contribution. Cheers!
@shwanky
Жыл бұрын
Great explanation. Thank you
@YashSharma-mp9so
2 жыл бұрын
Can anyone explain why we are using subset.copy() and why without it the output is an array with empty subsets??
@jaehoyang3565
Жыл бұрын
Because lists are mutable data types in Python.
@danaraujo7870
2 жыл бұрын
Why doesn't this terminate right away, since subset starts with len 0 and the first thing we check is if i is greater than or equal to subset, with i = 0? As in, i = 0, and len(subset) = 0, so why do we not terminate first thing?
@sozibrayhan1622
2 ай бұрын
Thank you very much
@tianmingguo8271
2 жыл бұрын
Best explanation ever!
@DU5T3
Жыл бұрын
i want to share my solution with u guys, i think this one is more syntactic sugar for me even if it uses the same algo, (ts solution) function subsets(nums: number[]): number[][] { return calc(0, nums, []); }; function calc(index: number, nums: number[], curr:number[] ) { if (index >= nums.length) return [curr]; let withx = calc(index + 1, nums, [...curr, nums[index]]); let withoutx = calc(index + 1, nums, curr); return [...withx, ...withoutx] }
@wingforce8530
11 ай бұрын
For this particular one, bfs would be cleaner and faster
@nayandhabarde
3 жыл бұрын
Can you post 1 for subset 2?
@ritikjain307
3 жыл бұрын
sorting is used to because element can be more than once. then set is used effectively. ans=set() temp=[] def dfs(index): if index==len(nums): ans.add(tuple(temp)) return temp.append(nums[index]) dfs(index+1) temp.pop() dfs(index+1) nums.sort() dfs(0) return ans
@DesignCell
2 жыл бұрын
@@ritikjain307 converting to sets with the tuple method makes this so simple! Thank you!
@chenzhuo9
3 жыл бұрын
great video, ty
@krzysztofsobocinski2207
2 жыл бұрын
You don't need backtracking at all. Simple iterative solution would be to iterate from 0 to 2^(size of array nums), check which bits are set in an iteration index and add corresponding element from array nums to current subset. And this is extremely easy to code.
@nniazoff
2 жыл бұрын
Great explanation!
@auroshisray9140
2 жыл бұрын
Backtracking with choices...great!!
@terlanibrahimli1191
3 ай бұрын
thanks , man !
@henryhan8838
2 ай бұрын
I have a concern. Isn't the time complexity like this, 2^(n+1) - 1, n = len(nums), ?
@adityaparab4314
Жыл бұрын
Is it me or understanding recursion and backtracking is a little difficult?
@Abubakar91718
11 ай бұрын
Its difficult but really a saviour. Very tough to grasp for a veginner😢
@adityaparab4314
11 ай бұрын
@@Abubakar91718 thanks! It's been 2 months after posting that comment now I feel I understand it better.
@OM-el6oy
3 жыл бұрын
why does doing the following lead to an incorrect solution? dfs(i + 1) subset.append(nums[i]) dfs(i+1) you did: subset.append(nums[i]) dfs(i+1) subset.pop() dfs(i+1) my logic with the first one is that you don't include nums[i] in the first dfs call but you do include it in the second one when you append nums[i] to subset. Evidently, my logic is wrong, an explanation would be appreciated.
@OM-el6oy
3 жыл бұрын
i see what I misundestood. my dfs just keeps calling itself till it gets to i = 3 and returns. Silly mistake
@where3639
2 жыл бұрын
That's because you need to remove the elements from the subset before traversing a new path in the decision tree. So, basically all you had to do was add subset.pop() as the final line in your code.
@SynapsePromotions
2 жыл бұрын
Had the same issue. My problem was that I forgot that since the subset we're editing is technically global, all changes persist even though we pop back up.
@muxa000
Жыл бұрын
@@where3639 Thank you very much! Had just the same question as @OM, now I do understand!
@bluejimmy168
2 жыл бұрын
At 2:25, why is it big o of( n * 2^n)? If it has 2^n sets aka powerset then shouldnt the big o be just big o of(2^n)? Where did the n come from?
@veliea5160
2 жыл бұрын
for ever index you are making 2 recursive calls. so time complexity for generating subsets is O(2^N). then you need to copy each subset to the res. How long does it take for each? Copying operation is related to the size of the subset, and worst case is when subset has n elements. So copying takes n
@schan263
2 жыл бұрын
@@veliea5160 You explained better than the video. In the video, the time complexity was given too early before the code was written. It's easier to see where the N comes from after seeing the code.
@rockmanvnx6
Жыл бұрын
@@veliea5160 Thank you so much, literally looking for this comment
@QuanNguyen-xq1jo
10 ай бұрын
@@veliea5160 oh man, this exactly what I m looking for after browsing the comments. Please upvote this
@SJ-fc6ke
2 жыл бұрын
How does the index value keep changing during recursion? I was debugging it and I noticed how the "i" value changes but did not understand how.
@ilanaizelman3993
2 жыл бұрын
CLEANNNN SOLUTION!
@raunakthakur7004
2 жыл бұрын
What is the complexity for this solution ? Time and Space
@yoshi4980
3 жыл бұрын
subset.copy() because this is a deep copy rather than a reference copy correct? great explanation otherwise. i've really over complicated this problem in the past and probably still do. the use of the dfs functon was clever : )
@NeetCode
3 жыл бұрын
Yup, that's exactly correct!
@rahulnegi456
2 жыл бұрын
the answer is still same? so what's the advantage of using copy()?
@pragyanprakhar9793
4 ай бұрын
00:03 Return all possible subsets of an array without duplicates. 01:09 The number of subsets of a given input is 2^n. 02:22 The worst case time complexity of this problem is n times 2 to the n 03:31 We can create four unique subsets by adding or not adding the element three. 04:33 We can generate subsets using backtracking. 05:40 Implementing backtracking depth first search algorithm 06:40 Implementing a depth-first search algorithm for generating subsets of a given set of numbers. 07:47 Implementing a depth-first search algorithm with different subsets
@raghavsood768
2 жыл бұрын
Could you please do Subsets - ii (Leetcode 90) as well? Thanks
@ethanking123
7 ай бұрын
The C++ solution on your website seems to be a direct copy from the LeetCode website, taking a different approach than the one presented in your video. This complicates the understanding of your video for those using C++. At times, when your explanation is a bit unclear, I find myself merging the code to better comprehend your explanation. However, when the code differs from your video, it becomes challenging to determine which approach I should follow.
@davidlee588
Жыл бұрын
Sir, I understand your code after your explanation. But when I use js to write out a successful code as yours in Python, I tried to visualize it by using debugger in vs code. I want to know how exactly the code runs. However, I'm totally lost, the "return" in the base case is where the i index decreases. Could you elaborate more on how the index changes so irregularly? The subset array length seems to have null influence on the change of the i index.
@davidlee588
Жыл бұрын
debugger; var subsets = function (nums) { let res = [], subset = []; const dfs = i => { if (i === nums.length) { res.push(subset.slice()); return; } subset.push(nums[i]); dfs(i + 1); subset.pop(); dfs(i + 1); }; dfs(0); return res; }; console.log(subsets([1, 2, 3]));
@ianokay
9 ай бұрын
This is so unintuitive it's wild. Code is often write once read many. So, in a practical sense, no code intended for humans should be written like this ever.
@indiasuhail
2 жыл бұрын
What is the run time of the solution? Is this O(n^2)?
@mementomori8856
2 жыл бұрын
Learned a lot, thanks! Also the TC can be improved to n^2 (n=length of input array) using Bit Manipulation.
@pftg
2 жыл бұрын
this is still n^2, because you should use bits as input not integers
@akshitkushwaha9479
8 ай бұрын
amazing. thanks
@tanoybhowmick8715
2 жыл бұрын
Thanks!
@dj1984x
Жыл бұрын
is the time complexity of this recursive algo O(2^n) or O(n*2^n)? I know neetcode says n*2^n, but several articles suggest it is 2^n. Several articles suggest it is n*2^n, I really have no idea lol. We know we have a total of 2^n solutions. Why is it times n?
@eslamwageh4461
10 ай бұрын
i dont know why also did u know why??
@siddeshsasane6223
8 ай бұрын
Appreciate it.
@afsalts5872
6 ай бұрын
Can some one tell me why deep copy was not used?
@almostworthy2973
Жыл бұрын
where is backtracking happening here?(Assuming Backtracking means not following that path where the solution doesn't exist.) It looks like a recursion where we are taking 2 decision at every step. Can some one explain please?
@linshen4658
Жыл бұрын
could you tell us what tool do you use to draw the graphs?
@andrewstrong1928
Жыл бұрын
the time complexity is not n * 2^n, it is just 2^n....
@vinayakgandhi5690
2 жыл бұрын
Why the time complexity is O(N*2^N) and not just O(2^N)? Can anyone please help?
@SunnySpaceCat
Жыл бұрын
I think he's saying it's n*2^n because the total number of subsets is 2^n and then for each one of those he has to run the copy() function, which worst case is O(N) time.
@emmatime2016
3 жыл бұрын
Very nice video.....
@m.y.7230
Ай бұрын
In drawing explanation he uses BFS and then in coding it's DFS. I could have been better explanation tbh
@user-vb5sg7di3l
Ай бұрын
Then create your own video
@kylea8968
2 жыл бұрын
thanks
@kartikhegde533
2 жыл бұрын
Can someone explain, when does subset.pop( ) line get executed?
@hamoodhabibi7026
2 жыл бұрын
It's when we want to do the right decision to add nothing (so revert our previous decision). In other words it's like doing root.right, but because we are just imitating a tree structure and we don;t actually have a root we are doing subset.pop()
@pamp3657
Жыл бұрын
good video
@Shailendrakumar-ge5cf
2 жыл бұрын
Liked and Subscribed :)
@SabinBajracharya
2 жыл бұрын
1) Solution in kotlin without mutating the array fun subsets(nums: IntArray): List { fun dfs(nums:IntArray, index: Int): List { if (index == 0) { return listOf(listOf(nums.first()), listOf()) } val res = dfs(nums, index - 1) return res + res.map { it + nums[index] } } return dfs(nums, nums.lastIndex) } 2) Iterative way without recursion fun subsets(nums: IntArray): List { val res = mutableListOf() for (num in nums) { var temp = mutableListOf() for (r in res) { val newList = r + num temp.add(newList) } res.addAll(temp) res.add(listOf(num)) } return res.apply{ add(listOf()) }.toList() } Also thank you for the video as I would not have been able to derive the recursive solution by myself if not for the Tree visualization.
Пікірлер: 187