Subsets - Backtracking - Leetcode 78

[@NeetCode]

💡 BACKTRACKING PLAYLIST: kzbin.info/www/bejne/ppfMgpKGiJaabqc

[@business_central]

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]

Really helpful. Great work !!

[@zoidian601]

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]

Its hard but if u just take an example and run through his function u will get to know what exactly is happening

[@zishiwu7757]

The general idea for backtracking seems to be 1. initialize global results array 2. figure out what the choices are at each step, in this case it is to add or not to add next element to subset 3. fgure out what is terminal condition, in this case when the index of the next element to add or not to add to subset is out of bounds of the nums array 4. figure out how to move the search towards the terminal condition so we don't get infinite loop, in this case increment by 1 the index of next element to select from nums 5. at the terminal condition, add the current result to the global results array 6. call backtrack at starting position 7. return global result array The other thing is to be able to recognize when to use backtrack. I think a good rule of thumb might be whenever you see problems that involve combinations that you know is going to be exponential and not linear O(n) or polynomial O(n^2) time.

[@localstreamers1054]

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.

[@radishanim]

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]

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]

Thank you for this explanation, this makes sense

[@jayeshpatil8408]

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!

[@E1an9640]

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]

reading this was really helpful. understanding recursion has been a nightmare for me. hopefully I get better by solving more problems

[@angelocortez1861]

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]

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.

[@rex1264]

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.

[@RichardLopez-lr4el]

Just had a coding interview, and this channel helped me so much! Keep up the amazing work!

[@anishm8813]

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]

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!

[@charanbathula984]

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]

[@pradgarimella]

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

[@Sportsandgames6]

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?

[@Eeeason-c5y]

great inspiration

[@The6thProgrammer]

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.

[@sap1363]

This is pure gold exactly what I wanted. Thanks for creating this gem

[@АлексейБлохин-ы8ш]

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]

This is how I did it. Much easier!

[@rustyglen7708]

Great video! I don't know how you find a way to explain hard problems so clearly. Thanks for uploading these!

[@aditijain2448]

i just love that all your videos are under 20 mins

[@almaspernshev7370]

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

[@ilanaizelman3993]

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]

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]

@@meowmaple u can use nums[:] as well

[@Zeegoner]

Uh, there is no nums.copy() in the entire video...

[@Zeegoner]

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]

@@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.

[@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

[@lhsh3942]

I was always running away from this question until saw this. Thanks for sharing this video~

[@pingpangqiu5605]

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

[@Codenames560]

wow 300 times better than other videos/leetcode solutions

[@tanmaymokal198]

Your videos are so fun to watch and most imp they don't make me sleep.

[@juliahuanlingtong6757]

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]

I feel the same....

[@adityakulkarni5577]

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)

[@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.

[@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

[@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.

[@DANIELEVI1234]

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]

Neet** sorry! :D

[@NeetCode]

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]

@@NeetCode Ah now it's clear, great! thank you!!

[@rabbyhossain6150]

@@NeetCode that means, if there is no copying then it is O(2^n)

[@kousikmitra7069]

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]

probably due to the copy() operation

[@theresabarton858]

Simpler solution: def subsets(self, nums: List[int]) -> List[List[int]]: output = [] def dfs(i, path): output.append(path[:]) for j in range(i, len(nums)): path.append(nums[j]) dfs(j + 1, path) path.pop() dfs(0, []) return output

[@chengjinfei8139]

I saw a lot ways to solve this issue, but you are the most clean one. Thanks.

[@noctua7771]

You're a legend at explaining things simply. Thank you!

[@KomalPal]

@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 ☺

[@edwardteach2]

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

[@BroskiXP]

A BRILLAINT SOLUTIONA GOOD SIR! WELL DONE.

[@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

[@surajslab984]

Your videos are really awesome, the way u explain the problem by splitting it into different section is simply great !!

[@deewademai]

backtracking question is the most difficult question to me. Where can I learn it and improve my skill with backtracking?

[@TanishBansal-ss2ou]

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

[@IvanTsurikov]

Once he drew the binary tree, I got the idea for this solution. It feels more intuitive. You append all the leaf nodes to `res`. ``` def find_subsets(nums): res = [] def dfs(i, subset, add: bool): if add: subset.append(nums[i]) if i == len(nums) - 1: res.append(subset[:]) # or subset.copy() return else: dfs(i + 1, subset[:], True) dfs(i + 1, subset[:], False) dfs(0, [], True) dfs(0, [], False) return res ```

[@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

[@GmDoggie]

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.

[@danny65769]

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)?

[@abhicasm9237]

Can someone explain me why we need to add the copy of subset there??

[@elyababakova2125]

Mindblowing🤯 Thanks for explanation, very helpful!

[@rajdipdas9413]

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.

[@sidazhong2019]

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.

[@saigopal4361]

such a clean solution ❤

[@bilalmohammad4242]

I love you man. keep up the great work !

[@kylehench]

Easy solution using list.extend() and list comprehension: res = [[]] for num in nums: res.extend([item + [num] for item in res]) return res

[@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

[@thereasonableprogrammer4921]

I'm struggling to understand the time complexity here. I get where 2^n is coming from (number of possible subsets in a powerset), but where is the *n coming from? Is this because we are copying the subset, which can be up to size n, for every node/leaf node?

[@hoyinli7462]

your code is super clean

[@SM-si2ky]

The tree is really helpful! Cheers

[@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] }

[@ThangTran-hi3es]

Thanks for your contribution. Cheers!

[@ghodsiyeghanbari7040]

Thank you, It was well-explained and neat!

[@ianokay]

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.

[@abhishektyagi3941]

Amazing video superb explnation..please make a video on subset2 also..

[@linshen4658]

could you tell us what tool do you use to draw the graphs?

[@nayandhabarde]

Can you post 1 for subset 2?

[@ritikjain307]

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]

@@ritikjain307 converting to sets with the tuple method makes this so simple! Thank you!

[@michaelyao9389]

I think we can also do this recursively.

[@OM-el6oy]

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]

i see what I misundestood. my dfs just keeps calling itself till it gets to i = 3 and returns. Silly mistake

[@where3639]

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]

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!

[@danaraujo7870]

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?

[@SJ-fc6ke]

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.

[@ethanking123]

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.

[@MAK_007]

the time complexity will be 2^n not n* 2^n

[@krzysztofsobocinski2207]

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.

[@indiasuhail]

What is the run time of the solution? Is this O(n^2)?

[@henryhan8838]

I have a concern. Isn't the time complexity like this, 2^(n+1) - 1, n = len(nums), ?

[@tianmingguo8271]

Best explanation ever！

[@yoshi4980]

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]

Yup, that's exactly correct!

[@rahulnegi456]

the answer is still same? so what's the advantage of using copy()?

[@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]));

[@wingforce8530]

For this particular one, bfs would be cleaner and faster

[@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]

i dont know why also did u know why??

[@raunakthakur7004]

What is the complexity for this solution ? Time and Space

[@adityaparab4314]

Is it me or understanding recursion and backtracking is a little difficult?

[@Abubakar91718]

Its difficult but really a saviour. Very tough to grasp for a veginner😢

[@adityaparab4314]

@@Abubakar91718 thanks! It's been 2 months after posting that comment now I feel I understand it better.

[@pragyanprakhar9793]

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

[@bluejimmy168]

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]

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]

@@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]

@@veliea5160 oh man, this exactly what I m looking for after browsing the comments. Please upvote this

[@mementomori8856]

Learned a lot, thanks! Also the TC can be improved to n^2 (n=length of input array) using Bit Manipulation.

[@pftg]

this is still n^2, because you should use bits as input not integers

[@nniazoff]

Great explanation!

[@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?

[@raghavsood768]

Could you please do Subsets - ii (Leetcode 90) as well? Thanks

[@YashSharma-mp9so]

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.

[@m.y.7230]

In drawing explanation he uses BFS and then in coding it's DFS. I could have been better explanation tbh

[@剑仙不想上学]

Then create your own video

[@sozibrayhan1622]

Thank you very much

[@GAnilKumar-h2p]

why does the backtracking solutions are much harder to understand

[@chenzhuo9]

great video, ty

[@terlanibrahimli1191]

thanks , man !

[@andrewstrong1928]

the time complexity is not n * 2^n, it is just 2^n....

[@ilanaizelman3993]

CLEANNNN SOLUTION!

[@auroshisray9140]

Backtracking with choices...great!!

[@afsalts5872]

Can some one tell me why deep copy was not used?

[@kartikhegde533]

Can someone explain, when does subset.pop( ) line get executed?

[@hamoodhabibi7026]

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()

[@rukmenip7028]

why is your website not working?

[@NeetCode]

Can you share more details? It's working for me and i haven't heard anyone else having issues.

[@akshitkushwaha9479]

amazing. thanks

[@siddeshsasane6223]

Appreciate it.

[@tanoybhowmick8715]

Thanks!