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.

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

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

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

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

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

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

[@АлексейБлохин-ы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!

[@sap1363]

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

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

[@rustyglen7708]

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

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

[@lhsh3942]

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

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

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

[@Codenames560]

wow 300 times better than other videos/leetcode solutions

[@aditijain2448]

i just love that all your videos are under 20 mins

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

[@tanmaymokal198]

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

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

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

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

[@noctua7771]

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

[@chengjinfei8139]

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

[@surajslab984]

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

[@saigopal4361]

such a clean solution ❤

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

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

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

[@hoyinli7462]

your code is super clean

[@BroskiXP]

A BRILLAINT SOLUTIONA GOOD SIR! WELL DONE.

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

[@elyababakova2125]

Mindblowing🤯 Thanks for explanation, very helpful!

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

[@marouaneakassab]

easier iterative solution: class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: cs = [[]] for num in nums: cs += [c+[num] for c in cs] return cs

[@TechWithKomal]

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

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

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

[@bilalmohammad4242]

I love you man. keep up the great work !

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

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

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

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

[@SM-si2ky]

The tree is really helpful! Cheers

[@ThangTran-hi3es]

Thanks for your contribution. Cheers!

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

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

[@tianmingguo8271]

Best explanation ever！

[@araneuskyuro]

Great explanation, thank you : )

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

[@ghodsiyeghanbari7040]

Thank you, It was well-explained and neat!

[@deewademai]

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

[@kylehench]

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

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

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

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

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

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

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

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

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

[@nniazoff]

Great explanation!

[@abhishektyagi3941]

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

[@wingforce8530]

For this particular one, bfs would be cleaner and faster

[@chenzhuo9]

great video, ty

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

[@ilanaizelman3993]

CLEANNNN SOLUTION!

[@auroshisray9140]

Backtracking with choices...great!!

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

[@sergiofranklin8809]

oh, I was wondering why it's two choices, because we have n, n-1, n-2.. number choices for each position. But turns out it was about "choose" or "not choose" number choices

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

[@sozibrayhan1622]

Thank you very much

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

[@linshen4658]

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

[@henryhan8838]

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

[@bokistotel]

I have a feeling that all this (leetcoding) is more about memorising than pure logic

[@joseph_p]

More pattern matching, but yea

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

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

[@indiasuhail]

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

[@terlan114]

thanks , man !

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

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

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

[@vinayakgandhi5690]

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.

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

[@michaelyao9389]

I think we can also do this recursively.

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

[@raghavsood768]

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

[@Shailendrakumar-ge5cf]

Liked and Subscribed :)

[@akshitkushwaha9479]

amazing. thanks

[@emmatime2016]

Very nice video.....

[@raunakthakur7004]

What is the complexity for this solution ? Time and Space

[@siddeshsasane6223]

Appreciate it.

[@tanoybhowmick8715]

Thanks!

[@MAK_007]

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