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!
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
@@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).
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
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.
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.
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.
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.
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.
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.
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
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!
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.
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
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.
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.
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
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]
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
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
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..
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
@@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.
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))
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
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.
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
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!
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.
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?
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.
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
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)?
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)
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?
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.
@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 ☺
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 ```
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
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
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.
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?
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.
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.
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.
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?
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
@@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.
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.
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.
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
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);
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.
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
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?
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 : )
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.
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.
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()
💡 BACKTRACKING PLAYLIST: th-cam.com/video/pfiQ_PS1g8E/w-d-xo.html
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!
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)
@@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).
mind blowing! Thx
what about [2], [2,3] and []?
Really helpful. Great work !!
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
Its hard but if u just take an example and run through his function u will get to know what exactly is happening
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.
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.
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]]
Thank you for this explanation, this makes sense
Thanks for the explaination! I didn't get it before! :)
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.
Thanks, buddy!
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.
Just had a coding interview, and this channel helped me so much! Keep up the amazing work!
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.
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.
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
reading this was really helpful. understanding recursion has been a nightmare for me. hopefully I get better by solving more problems
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!
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
Great thanks for the explanation!!!
Can you share the backtracking solution then?
great inspiration
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.
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.
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.
Who said that the input array has no duplicates? If that's true the solutions here are okay.
@@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!
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.
Great video! I don't know how you find a way to explain hard problems so clearly. Thanks for uploading these!
This is pure gold exactly what I wanted. Thanks for creating this gem
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
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]
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
This is how I did it. Much easier!
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
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..
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
@@meowmaple u can use nums[:] as well
Uh, there is no nums.copy() in the entire video...
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.
@@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.
i just love that all your videos are under 20 mins
Your videos are so fun to watch and most imp they don't make me sleep.
I was always running away from this question until saw this. Thanks for sharing this video~
wow 300 times better than other videos/leetcode solutions
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))
probably due to the copy() operation
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
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.
such a clean solution ❤
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
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!
I feel the same....
I saw a lot ways to solve this issue, but you are the most clean one. Thanks.
You're a legend at explaining things simply. Thank you!
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.
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?
Your videos are really awesome, the way u explain the problem by splitting it into different section is simply great !!
Hello Neat Code!
Your work is amazing and really helpful!
Can you please elaborate about the Time and Space complexities?
Thank you very much
Neet** sorry! :D
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.
@@NeetCode Ah now it's clear, great! thank you!!
@@NeetCode that means, if there is no copying then it is O(2^n)
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
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)?
backtracking question is the most difficult question to me. Where can I learn it and improve my skill with backtracking?
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)
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?
yeah same qs
A BRILLAINT SOLUTIONA GOOD SIR! WELL DONE.
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.
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
Mindblowing🤯
Thanks for explanation, very helpful!
Pls show the inner implementation of this code using stack I couldn't able to understand what is happening after poping out the element
@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 ☺
Easy solution using list.extend() and list comprehension:
res = [[]]
for num in nums:
res.extend([item + [num] for item in res])
return res
your code is super clean
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
```
Can someone explain me why we need to add the copy of subset there??
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
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
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
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.
The tree is really helpful! Cheers
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?
I have a concern. Isn't the time complexity like this, 2^(n+1) - 1, n = len(nums), ?
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.
i see what I misundestood. my dfs just keeps calling itself till it gets to i = 3 and returns. Silly mistake
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.
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.
@@where3639 Thank you very much! Had just the same question as @OM, now I do understand!
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.
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?
i dont know why also did u know why??
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?
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
@@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.
@@veliea5160 Thank you so much, literally looking for this comment
@@veliea5160 oh man, this exactly what I m looking for after browsing the comments. Please upvote this
Thanks for your contribution. Cheers!
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.
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.
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]));
Thank you, It was well-explained and neat!
I love you man. keep up the great work !
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
could you tell us what tool do you use to draw the graphs?
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]
}
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.
Amazing video superb explnation..please make a video on subset2 also..
I think we can also do this recursively.
What is the run time of the solution? Is this O(n^2)?
Can you post 1 for subset 2?
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
@@ritikjain307 converting to sets with the tuple method makes this so simple! Thank you!
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?
Can anyone explain why we are using subset.copy() and why without it the output is an array with empty subsets??
Because lists are mutable data types in Python.
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.
Best explanation ever！
What is the complexity for this solution ? Time and Space
Thank you very much
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 : )
Yup, that's exactly correct!
the answer is still same? so what's the advantage of using copy()?
For this particular one, bfs would be cleaner and faster
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.
the time complexity will be 2^n
not n* 2^n
Great explanation!
Learned a lot, thanks! Also the TC can be improved to n^2 (n=length of input array) using Bit Manipulation.
this is still n^2, because you should use bits as input not integers
Could you please do Subsets - ii (Leetcode 90) as well?
Thanks
Is it me or understanding recursion and backtracking is a little difficult?
Its difficult but really a saviour. Very tough to grasp for a veginner😢
@@Abubakar91718 thanks! It's been 2 months after posting that comment now I feel I understand it better.
great video, ty
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
CLEANNNN SOLUTION!
thanks , man !
the time complexity is not n * 2^n, it is just 2^n....
Can some one tell me why deep copy was not used?
Backtracking with choices...great!!
Why the time complexity is O(N*2^N) and not just O(2^N)? Can anyone please help?
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.
Can someone explain, when does subset.pop( ) line get executed?
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()
Thanks!
amazing. thanks
good video
thanks